# 0208. Implement Trie (Prefix Tree)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0208-implement-trie-prefix-tree)

A [**trie**](https://en.wikipedia.org/wiki/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.
  {% endtab %}

{% tab title="✍🏻 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
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Trie data structure can be implemented by the **nested hash table (`dict`).**
{% endhint %}

> **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.**
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
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

```

{% endtab %}

{% tab title="🤖 Java" %}

```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 );
    }
}
```

{% endtab %}
{% endtabs %}