# Prefix Tree

## Intro

We can consider trie as a space efficient hash table for words. It supports add(word) and contains(word) in O(len(word)) time. Trie saves space because it stores words with common prefixes under the same path.

## Implement Trie ([LC.208](https://leetcode.com/problems/implement-trie-prefix-tree/))

> Implement a trie with insert, search, and startsWith methods.
>
> * insert - Inserts a word into the trie
> * search - Returns if the word is in the trie
> * startsWith - Returns if there is any word in the trie that starts with the given prefix

## Example

```
Trie trie = new Trie();
trie.insert("lol");
if (trie.search(word)) freqMap.get(word)++;
if (trie.startsWith(prefix)) freqMap.get(prefix)++;
```

## Analysis

Trie is a n-ary tree depending on the number of available characters. Each node should hold its children map, (and its own key?), and isWord boolean. Internally, we want to store a dummyRoot to signify the empty string prefix.

## Code

```java
public class Trie {
    private class TrieNode {
        Map<Character, TrieNode> children;
        Boolean isWord;
        public TrieNode() {
            children = new HashMap<Character, TrieNode>();
            isWord = false;
        }
    }

    TrieNode dummyRoot;

    public Trie() {
        dummyRoot = new TrieNode();
    }

    /** 
     * Inserts a word into the trie. 
     */
    public void insert(String word) {
        TrieNode current = dummyRoot;
        for (int i = 0; i < word.length(); i++) {
            char letter = word.charAt(i);
            if (!current.children.containsKey(letter)) {
                current.children.put(letter, new TrieNode());
            }
            current = current.children.get(letter);
        }
        current.isWord = true;
    }

    /** 
     * Returns if the word is in the trie. 
     */
    public boolean search(String word) {
        return searchPrefix(word) != null && searchPrefix(word).isWord;
    }

    /** 
     * Returns if there is any word in the trie that starts with the given prefix. 
     */
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    /**
     * Search the prefix tree for the word
     * @return the node that matches the last character in word, null if no match
     */
    private TrieNode searchPrefix(String word) {
        TrieNode travel = dummyRoot;
        for (int i = 0; i < word.length(); i++) {
            char letter = word.charAt(i);
            if (travel.children.containsKey(letter)) {
                travel = travel.children.get(letter);
            } else {
                return null;
            }
        }
        return travel;
    }
}
```

## Follow Up #1 ([LC.211](https://leetcode.com/problems/add-and-search-word-data-structure-design/description/))

The search query can contain `.` which matches any character.

## Example

```
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
```

## Analysis

Before, we use a travel pointer to travel down a path (just like traversing a linked list). Now, in order to support `.`, we need to explore an entire subtree to find a match. Preform a DFS on all the possible children at that level and then figure out one path that matches with the given word.

## Code

```java
/** 
 * Returns if the word is in the data structure. 
 * A word could contain the dot character '.' to represent any one letter. 
 */
public boolean search(String word) {
    return searchWord(word, dummyRoot, 0);
}

private boolean searchWord(String word, TrieNode curNode, int curIndex) {  
    // base case
    if (word.length() == curIndex) {    
        return curNode.isWord;
    }
    // search
    char curLetter = word.charAt(curIndex);
    if (curLetter == '.') {
        for (Character match : curNode.children.keySet()) {
            if (searchWord(word, curNode.children.get(match), curIndex + 1)) {
                return true;
            }
        }
    } else {
        if (curNode.children.containsKey(curLetter)) {
            return searchWord(word, curNode.children.get(curLetter), curIndex + 1);
        } else {
            return false;
        }
    }
    return false;
}
```

## Follow Up #2

The search query can contain `*` which can match 0 or more previous character.

## References

* UMD CS420 Lecture 23 [Tries & Suffix Trees](https://www.cs.umd.edu/class/spring2008/cmsc420/L23.SuffixTrees.pdf)
* Implement Trie [Editoral Solution](https://leetcode.com/articles/implement-trie-prefix-tree/)
* Wikipedia [Prefix Tree](https://en.wikipedia.org/wiki/Trie), [Compact Prefix Tree](https://en.wikipedia.org/wiki/Radix_tree)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-4/advanced_data_structures/text-data/trie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.