0208. Implement Trie (Prefix Tree)

Medium | Design + String | 112 ms (99.40%), 29.6 MB (93.89%)

❓ Problem Statement

Source: LeetCode - Implement Trie (Prefix Tree) GitHub: Solution / Performance

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.

• void insert(String word) Inserts the string word into the trie.

• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.

• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

✍🏻 Constraints & Example

💡 Ideas

Trie data structure can be implemented by the nested hash table (dict).

Insert

Iterate each char in the word and insert each of them into the hash table. Note that the symbol that represents the end of the word also needs to be added. (Here I use #)

Search

To search for a certain word, we iterate each char in the word and check the existence of each of them. Besides, if the search operation is done for each char, check whether the symbol # exists in the current node or not.

StartWith

Almost the same as the search operation. Except that we don't need to check the symbol # since the input string is only a prefix.

🤖 Python3

class Trie:

    def __init__(self):
        self.root = {}
        

    def insert(self, word: str) -> None:
        # time  : O(n), n is the lenght of str
        # space : O(n)
        
        cur = self.root
        
        for char in word:
            if char not in cur: cur[char] = {}            
            cur = cur[char]
            
        cur['#'] = True
        

    def search(self, word: str) -> bool:
        # time  : O(n)
        # space : O(1)
        
        cur = self.root
        
        for char in word:
            if char not in cur: return False
            cur = cur[char]
            
        return '#' in cur
        

    def startsWith(self, prefix: str) -> bool:
        # time  : O(n)
        # space : O(1)
        
        cur = self.root
        
        for char in prefix:
            if char not in cur: return False
            cur = cur[char]
            
        return True

🤖 Java