208 Implement Trie (Prefix Tree)

1. Question

Implement a trie withinsert,search, andstartsWithmethods.
Note: You may assume that all inputs are consist of lowercase lettersa-z.

2. Implementation

class Trie {
class TrieNode {
char val;
boolean isWord;
TrieNode[] childNode;
public TrieNode(char val) {
this.val = val;
childNode = new TrieNode[26];
}
}
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode(' ');
}
/** Inserts a word into the trie. */
public void insert(String word) {
if (word == null || word.length() == 0) {
return;
}
TrieNode curNode = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (curNode.childNode[index] == null) {
curNode.childNode[index] = new TrieNode(c);
}
curNode = curNode.childNode[index];
}
curNode.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
if (word == null || word.length() == 0) {
return false;
}
TrieNode curNode = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (curNode.childNode[index] == null) {
return false;
}
curNode = curNode.childNode[index];
}
return curNode.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
if (prefix == null || prefix.length() == 0) {
return false;
}
TrieNode curNode = root;
for (char c : prefix.toCharArray()) {
int index = c - 'a';
if (curNode.childNode[index] == null) {
return false;
}
curNode = curNode.childNode[index];
}
return true;
}
}
/**
* 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);
*/

3. Time & Space Complexity

时间复杂度: inset:O(L), search: O(L), startsWith: O(L), L 为输入string的长度
空间复杂度: O(L)