Implement a trie with insert, search, and startsWith methods.
Example
1 2 3 4 5 6 7 8
|
Trie trie = new Trie();
trie.insert("apple"); trie.search("apple"); trie.search("app"); trie.startsWith("app"); trie.insert("app"); trie.search("app");
|
Note
- You may assume that all inputs are consist of lowercase letters a-z.
- All inputs are guaranteed to be non-empty strings.
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
|
public class { private boolean word; private TrieNode[] children = new TrieNode[26]; }
private TrieNode root;
public Trie() { this.root = new TrieNode(); }
public void insert(String word) { TrieNode node = root;
for (int i = 0; i < word.length(); i++) { int idx = word.charAt(i) - 'a';
if (node.children[idx] == null) node.children[idx] = new TrieNode();
node = node.children[idx]; }
node.word = true; }
public boolean search(String word) { TrieNode node = find(word); return node != null && node.word; }
public boolean startsWith(String prefix) { TrieNode node = find(prefix); return node != null; }
private TrieNode find(String prefix) { TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) { int idx = prefix.charAt(i) - 'a';
if (node.children[idx] == null) return null;
node = node.children[idx]; }
return node; }
|
近期评论