# 208. Implement Trie (Prefix Tree) (Medium)

https://leetcode.com/problems/implement-trie-prefix-tree/

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.

## Solutions

``````class Trie {
// This problem is quite trivial and requires mass caution.

String sequence = "";
String word = null;

Map<Character, Trie> subTries = new HashMap<>();

/** Initialize your data structure here. */
public Trie() {

}

// TODO when we process the ith char in the word, the ith char should not be included by current trie.

// create trie node for ith node
private void insert(String word, int i) {

// current word ending at i represents current trie is not only a prefix trie, there
// are also words affiliate to it.

// FIXME below commented out statements are incorrect
/*
if (i == word.length() - 1) {
this.word = word;
}
*/

if (i == word.length()) {
this.word = word;

// do not forget below one
this.sequence = word.substring(0, i);

return;
}

// substring(i) means trunk the string starting from i, not ending to i

// I made a mistake word.substring(0, i + 1), actually, ith char should not be included
// for current trie
this.sequence = word.substring(0, i);

char c = word.charAt(i);
// create a sub trie if not exists
if (!subTries.keySet().contains(c)) {
subTries.put(c, new Trie());
}

subTries.get(c).insert(word, i + 1);
}

/** Inserts a word into the trie. */
public void insert(String word) {
this.insert(word, 0);
}

private boolean search(String word, int i) {
// the exit
if (i == word.length()) {
// this.word != null indicates it's not only a prefix, but also representing a word.
if (this.word != null && this.word.equals(word)) {
return true;
}

return false;
}

char c = word.charAt(i);
if (!subTries.keySet().contains(c)) {
return false;
}

return subTries.get(c).search(word, i + 1);
}

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

private boolean startsWith(String prefix, int i) {
// the exit
if (i == prefix.length()) {
if (this.sequence.equals(prefix)) {
return true;
}

return false;
}

char c = prefix.charAt(i);
if (!subTries.keySet().contains(c)) {
return false;
}

return subTries.get(c).startsWith(prefix, i + 1);
}

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