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

Constraints:

• 1 <= word.length, prefix.length <= 2000

• word and prefix consist only of lowercase English letters.

• At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Input:
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output:
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

💡 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

class Trie {
    Trie[]  arr;
    boolean wordEnd;
    
    /*  Initialize your data structure here  */
    public Trie() {
        arr = new Trie[26];
    }
    
    
    /*  Inserts a word into the trie  */
    public void insert(String word) {
        insert( word, 0 );
    }
    
    private void insert(String word, int i) {
        if( i == word.length() ) {
            wordEnd = true;
            return;
        }
        
        int index = word.charAt(i) - 'a';
        if( arr[index] == null ) arr[index] = new Trie();
        
        arr[index].insert(word, i + 1);
    }
    
    
    /*  Returns if the word is in the trie  */
    public boolean search(String word) {
        return search( word, 0 );
    }
    
    private boolean search(String word, int i) {
        if( i == word.length() ) return wordEnd;
        
        int index = word.charAt(i) - 'a';
        
        if( arr[index] == null ) return false;
        else return arr[index].search( word, i + 1 );
    }
    
    
    /*  Returns if there is any word in the trie that starts with the given prefix  */
    public boolean startsWith(String prefix) {
        return startsWith( prefix, 0 );
    }
    
    public boolean startsWith(String prefix, int i) {
        if( i == prefix.length() ) return true;
        
        int index = prefix.charAt(i) - 'a';
        
        if( arr[index] == null ) return false;
        else return arr[index].startsWith( prefix, i + 1 );
    }
}