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
}

See all trie tree problems: #trie

See more blog posts.

Post Views: 11