我们使用搜索引擎时，需要在搜索框输入关键字，当你在框中输入头几个字符时，搜索框会出现一个下拉框，里面包含着以当前输入字符为前缀的字符串，如果里面包含你想要输入的内容，那么你就可以直接选取，而不必要把关键字的所有字符依次输入，这种功能极大的提高了搜索体验。
本次算法题的题目是，你如何设计该功能。例如给你一组关键词：to, tea, ted, in, inn. 当用户输入’t’的时候，你要把以’t’开头的所有单词返回给用户。
这道算法题的解决涉及到一种树形结构叫字典树，其具体结构如下：
当给定一个字符t时，我们从树的根节点走到左边以字符t开头的子树，这颗子树的叶子节点就是我们要返回给用户的所有单词。假设单词是有26个小写字母组成的，那么字典树的每个节点最多可以有26个孩子节点。我们先看看树节点如何定义：
import java.util.ArrayList;
import java.util.HashMap;
public class TrieNode {
private HashMap<Byte, TrieNode> map = new HashMap<Byte, TrieNode>();
private String s = "";
public void setString(String str) {
this.s = str;
}
public String getString() {
return s;
}
public TrieNode nextNode(Byte b) {
if (map.get(b) == null) {
TrieNode n = new TrieNode();
map.put(b, n);
}
return map.get(b);
}
public TrieNode getNode(Byte b) {
return map.get(b);
}
public ArrayList<TrieNode> getAllNextNodes() {
ArrayList<TrieNode> arr = new ArrayList<TrieNode>();
for (char c = 'a'; c <= 'z'; c++) {
if (map.get((byte)c) != null) {
arr.add(map.get((byte)c));
}
}
return arr;
}
}TrieNode 类中有个map,它的作用在于指向孩子节点，给定一个字符，从该哈希表中得到的节点，就是以该字符开头的子多叉树的根节点。如果节点是叶子节点，那么该节点就包含了其对应的字符串，例如上图中的编号为3，4，5，7，9，11，12，15。从根节点开始抵达到叶子节点的每一条路径都对应一个字符，所有这些字符组合起来就是叶子节点对应的字符串。
注意到，拥有相同祖先的叶子节点所包含的字符串都有着相同的前缀，例如节点“tea”, “ted”,”ten”,他们的父节点是”te”,从根节点要抵达这些叶子节点，那必须先从根节点到达节点”te”。
我们再看看给定一组字符串，如何根据字符串构造一颗字典树，代码如下：
import java.util.ArrayList;
import java.util.Stack;
public class TrieBuilder {
private TrieNode root = null;
private Stack<TrieNode> stack = new Stack<TrieNode>();
public void addWord(String s) {
if (root == null) {
root = new TrieNode();
}
TrieNode node = root;
int l = 0;
while (l < s.length()) {
node = node.nextNode((byte)s.charAt(l));
l++;
}
node.setString(s);
}
private void addNodeListToStack(ArrayList<TrieNode> nodes) {
for (int i = 0; i < nodes.size(); i++) {
stack.push(nodes.get(i));
}
}
public ArrayList<String> getAllWordsByPrefix(String prefix) {
int l = 0;
TrieNode node = root;
while (l < prefix.length() ) {
node = node.getNode((byte)prefix.charAt(l));
if (node == null) {
break;
}
l++;
}
if (node == null) {
return null;
}
addNodeListToStack(node.getAllNextNodes());
ArrayList<String> allWords = new ArrayList<String>();
while (stack.empty() == false) {
TrieNode n = stack.pop();
if (n.getString().isEmpty() == false) {
allWords.add(n.getString());
}
addNodeListToStack(n.getAllNextNodes());
}
return allWords;
}
}addWords接口根据给定字符串构造相应节点，根据字符串中的每个字符，调用TrieNode的nextNode接口，它从节点的map中查看是否有对应于给定字符的子节点，如果没有，则构造一个新节点，加入当前节点的map.
addNodeListToStack把给定节点的所有子节点加入堆栈，例如对于节点”te”，其有三个子节点：“tea”,”ted”,”ten”, 着三个节点将会被压到堆栈上。
getAllWordsByPrefix根据前缀字符串，找到所有已该字符串为前缀的关键字，例如给定前缀字符串为”t”, 那么该函数先从多叉树中找到以t开头的子树，然后把其所有子节点压入堆栈，根据图中所示多叉树，以t开头的子树，其根节点含有两个子节点，分别是”to”, 和 “te”, 于是代码把这两个节点压入堆栈，然后再从堆栈弹出，弹出时查看该节点是否含有关键词字符串，当子节点”to”被弹出堆栈时，它含有关键词”to”,那么代码把这个关键词加入队列，当节点”te”被弹出堆栈时，该节点不含有关键词，于是代码继续把该节点的所有子节点”tea”,”ted”,”ten”压入堆栈，然后再把堆栈中的节点弹出，做相同操作，当堆栈所有节点处理完毕后，拥有给定字符串为前缀的所有关键字字符串就包含在一个队列中了。
最后我们看看主入口的代码：
import java.util.ArrayList;
public class BinaryTree {
public static void main(String[] s) {
String[] dictionary = new String[]{"tea", "to", "ted", "ten", "A", "in", "inn"};
TrieBuilder tb = new TrieBuilder();
for (int i = 0; i < dictionary.length; i++) {
tb.addWord(dictionary[i]);
}
ArrayList<String> prefixWords = tb.getAllWordsByPrefix("t");
System.out.println("words with prefix of t are:");
for (int i = 0; i < prefixWords.size(); i++) {
System.out.print(prefixWords.get(i) + " ");
}
}
}代码先构造一组关键词，然后根据关键词字符串，调用TrieBuilder的addWords接口，构造给定字典树，最后通过前缀字符串”t”,找到所有以字符t开头的关键字，上面代码运行后结果如下：
words with prefix of t are:
to ten ted tea从结果判定，我们代码的实现能满足题目要求的效果。算法的运行效率与给定前缀的关键字长度有关，如果关键字的最大长度为n, 那么算法的效率就是O(n),字典树的空间效率也跟关键字的长度相关，如果关键字的最大长度为s,那么算法的空间复杂度为O(s).
更详细的讲解以及代码调试演示，请参看视频。
更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：
