# implement-trie

## Problem

[Implement Trie(prefix Tree)](https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/535/week-2-may-8th-may-14th/3329/)

## Problem Description

```
Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true
Note:

You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.
```

## Solution

First understand what is trie, please read [Trie (Wiki)](https://en.m.wikipedia.org/wiki/Trie).

Now define TrieNode with char, isWord, children. 1. do insert:

* iterate through each char in word, check whether current char ch in current node's children. if not, create new TrieNode(ch), put into current node children, other wise do nothing 
* then reset current node as curr.children.get(ch).
* after word, set current node isWord = true.
  1. do search:
* iterate through each char in word, for each ch:
  * if ch is in current node children, continue, if not in current node's children, return false. terminate early. 
  * reset current node as curr.children.get(ch), (go next level)
  * until at last char, check current node isWord is true or not, if isWord = true, return true. otherwise no word in trie. 
    1. do prefix search:
* same search steps as search word. 
* at last step, return true (meaning it has prefix, do need to check isWord).

For example:

![Implement Trie](/files/-M7LzWPwTNvtCr-t6f4A)

### Complexity Analysis

**insert(word)**: `O(n) -- n is the length of word`

**search(word)**: `O(n) -- n is the length of word`

### Code

```java
class Trie {
    TrieNode root;
    /** Initialize your data structure here. */
   public Trie() {
        root = new TrieNode();
   }

   /** Inserts a word into the trie. */
   public void insert(String word) {
       TrieNode curr = root;
       for (char ch : word.toCharArray()) {
            if (!curr.children.containsKey(ch)) {
                 curr.children.put(ch, new TrieNode(ch));

            }
            curr = curr.children.get(ch);

       }
       curr.isWord = true;
   }

   /** Returns if the word is in the trie. */
   public boolean search(String word) {
       return isWordOrPrefix(word, true);
   }

   /** Returns if there is any word in the trie that starts with the given prefix. */
   public boolean startsWith(String prefix) {
       return isWordOrPrefix(prefix, false);
   }

   private boolean isWordOrPrefix(String prefix, boolean isWord) {
       TrieNode curr = root;
       for (char ch : prefix.toCharArray()) {
           if (!curr.children.containsKey(ch)) return false;
               curr = curr.children.get(ch);
       }
       return isWord ? curr.isWord : true; 
   }

}

class TrieNode {
    char ch;
    boolean isWord;
    Map<Character, TrieNode> children;
    public TrieNode(char ch) {
        this.ch = ch;
        isWord = false;
        children = new HashMap<>();
    }
    public TrieNode() {
       isWord = false;
       children = new HashMap<>();
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */
```


---

# 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://snowan.gitbook.io/study-notes/leetcode/may2020challenge/implement-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.