完了還剩20多分鐘就是在線做一道類似瀏覽器輸入keyword搜索給出提示這樣的題。自然用trie來做逞带，和leetcode 208差不多陌兑，不同的是輸入prefix，返回所有單詞（dfs或bfs均可）偷厦。
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=201846&highlight=snapchat
My code:
// get string using prefix
private TrieNode root = new TrieNode('r');
public List<String> prefixString(String prefix, String[] arr) {
buildTrie(arr);
TrieNode node = search(prefix, 0, root);
List<String> ret = new ArrayList<String>();
if (node == null) {
return null;
}
dfs(node, ret);
return ret;
}
private void dfs(TrieNode root, List<String> ret) {
if (root.isWord) {
ret.add(root.s);
}
for (int i = 0; i < 26; i++) {
if (root.next[i] != null) {
dfs(root.next[i], ret);
}
}
}
private void buildTrie(String[] arr) {
for (String s : arr) {
insert(s, 0, root);
}
}
private void insert(String s, int index, TrieNode root) {
if (index >= s.length()) {
root.isWord = true;
root.s = s;
}
else {
char curr = s.charAt(index);
if (root.next[curr - 'a'] == null) {
root.next[curr - 'a'] = new TrieNode(curr);
}
insert(s, index + 1, root.next[curr - 'a']);
}
}
private TrieNode search(String s, int index, TrieNode root) {
if (index >= s.length()) {
return root;
}
char curr = s.charAt(index);
if (root.next[curr - 'a'] == null) {
return null;
}
return search(s, index + 1, root.next[curr - 'a']);
}
class TrieNode {
TrieNode[] next = new TrieNode[26];
char val;
boolean isWord;
String s;
TrieNode(char val) {
this.val = val;
}
}
Anyway, Good luck, Richardo! -- 09/27/2016
