Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

Review: Trie Tree Problems

Posted on January 22, 2018July 26, 2020 by braindenny

Trie tree is good at prefix-searching requirements.

Key operations: insert, search, prefix, getHeight, etc.



Basic Abstractions

Name Summary
children map[byte]*Trie Use pointer
Common Trie operations Insert/Search/StartsWith
Sometimes no need to track isLeaf LeetCode: Word Squares
Trie for inverted index LeetCode: Stream of Characters

Suffix tree: wikipedia link

Name Summary
Count of distinct substrings of a string using Suffix Trie  
Generate all unique substrings for given string stackoverflow link
Finding the longest repeated substring  
Finding the longest common substring Longest common substring problem
Finding the longest palindrome in a string  

Top Questions

Num Problem Summary
1 Fuzzy match for tolerance of one difference LeetCode: Implement Magic Dictionary
2 Graph with next steps by a trie Leetcode: Word Search II
3 Trie for bit manipulation LeetCode: Maximum XOR of Two Numbers in an Array
4 Trie with a live data stream Leetcode: Stream of Characters
## Blog link: https://code.dennyzhang.com/add-and-search-word-data-structure-design
## Basic Ideas: Trie tree. Search with dfs or backtracking
##              TrieNode: children
##     search doesn't necessarily means startswith
##     If add you "word" and "words", then ask you whether "word" exists. You should say True
## Complexity: Time O(n), Space O(n), n how many nodes in the Trie Tree

class TrieNode(object):
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.is_word = False

class WordDictionary(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        node = self.root
        for ch in word:
            node = node.children[ch]
        node.is_word = True

    def search(self, word):
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        return self.mysearch(word, self.root)

    def mysearch(self, word, node):
        if len(word) == 0:
            # if node.is_word is False, we get a prefix, instead of a match.
            return node.is_word is True

        ch = word[0]
        if ch != '.':
            if ch not in node.children:
                return False
            return self.mysearch(word[1:], node.children[ch])
        else:
            for child in node.children.values():
                if self.mysearch(word[1:], child) is True:
                    return True
            return False

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

Scenarios

type Trie struct {
    children map[byte]*Trie
    isLeaf bool
}

Code Skeleton

  • Solution: trie with extra datastructure in leaf nodes
// https://code.dennyzhang.com/word-search-ii
type Trie struct {
    children map[byte]*Trie
    isLeaf bool
    index int
}

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups

See all trie tree problems: #trie

  • Review: Trie Tree Problems
  • LeetCode: Word Squares
  • LeetCode: Word Search II
  • LeetCode: Stream of Characters
  • LeetCode: Short Encoding of Words
  • LeetCode: Replace Words
  • LeetCode: Remove Sub-Folders from the Filesystem
  • LeetCode: Prefix and Suffix Search
  • LeetCode: Maximum XOR of Two Numbers in an Array
  • LeetCode: Map Sum Pairs
  • LeetCode: Longest Word in Dictionary
  • LeetCode: Implement Trie (Prefix Tree)
  • LeetCode: Implement Magic Dictionary
  • LeetCode: Add and Search Word – Data structure design

See more blog posts.

linkedin
github
slack

Post Views: 11
Posted in ReviewTagged #trie, review

Post navigation

Review: Linked List Problems
LeetCode: Unique Letter String

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.