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