# implement-trie

## Problem

Implement Trie(prefix Tree)

## 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

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:

### Complexity Analysis

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

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

### Code

``````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);
*/``````

Last updated