trie.md

Trie (Prefix Tree)

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

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        current = self.root
        for letter in word:
            current = current.children[letter]
        current.is_word = True

    def search(self, word):
        current = self.root
        for letter in word:
            current = current.children.get(letter)
            if current is None:
                return False
        return current.is_word

    def startsWith(self, prefix):
        current = self.root
        for letter in prefix:
            current = current.children.get(letter)
            if current is None:
                return False
        return True

Practice:

• 720. Longest Word in Dictionary
• 208. Implement Trie (Prefix Tree)
• 648. Replace Words
• 677. Map Sum Pairs
• 1268. Search Suggestions System
• 676. Implement Magic Dictionary
• 1023. Camelcase Matching

Reference:

• Implementing a Trie in Python (in less than 100 lines of code)