Problem
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
Trie data structure is a multi-node tree. While tree Node as 2 child node, trie node has 26 child node stored in an array. It has an additional boolean field marking the end of a word.
import java.util.*;
class Solution {
public static void main(String...args) {
Trie trie = new Trie();
trie.insert("apple");
System.out.println(trie.search("apple")); // returns true
System.out.println(trie.search("app")); // returns false
System.out.println(trie.startsWith("app")); // returns true
trie.insert("app");
System.out.println(trie.search("app")); // returns true
}
}
class Trie {
TrieNode root;
private static class TrieNode {
TrieNode[] next = new TrieNode[26];
boolean isEnd = false;
}
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) { //apple
insert(root, word, 0);
}
private void insert(TrieNode node, String word, int n) { //1
if(n == word.length()) {
return;
}
int p = word.charAt(n) - 'a';
TrieNode next = node.next[p];
if(next == null) {
next = new TrieNode();
node.next[p] = next;
}
if(n == word.length() - 1) {
next.isEnd = true;
}
insert(next, word, n+1);
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
return search(root, word, 0);
}
private boolean search(TrieNode node, String word, int n) {
int p = word.charAt(n) - 'a';
TrieNode next = node.next[p];
if(next == null) {
return false;
} else {
if(n == word.length() - 1) {
return next.isEnd;
}
return search(next, word, n+1);
}
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
return startsWith(root, prefix, 0);
}
private boolean startsWith(TrieNode node, String word, int n) {
int p = word.charAt(n) - 'a';
TrieNode next = node.next[p];
if(next == null) {
return false;
} else {
if(n == word.length() - 1) {
return true;
}
return startsWith(next, word, n+1);
}
}
}
The time complexity is O(w) for all 3 operations, where w is the length of word. We need to process each character in the word of length w.
The space complexity is O(w) for all 3 operations.
- For insert, we create w TrieNode, TrieNode has a size 26 array and a boolean field, we assume its size is constant.
- For search and startsWith, the recursive call stack is w layer deep, so the space also proportional to O(w).
