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 ProblemsLeetCode: Word SquaresLeetCode: Word Search IILeetCode: Stream of CharactersLeetCode: Short Encoding of WordsLeetCode: Replace WordsLeetCode: Remove Sub-Folders from the FilesystemLeetCode: Prefix and Suffix SearchLeetCode: Maximum XOR of Two Numbers in an ArrayLeetCode: Map Sum PairsLeetCode: Longest Word in DictionaryLeetCode: Implement Trie (Prefix Tree)LeetCode: Implement Magic DictionaryLeetCode: Add and Search Word – Data structure design See more blog posts. Post Views: 11