什么是字典树（Trie）

解决什么问题

我们有如下需求，给出4*4的字母表，我们可以通过把相邻（横向、竖向、斜向都算相邻）的字母连接起来组成一个单词，要找到所有单词。像下图画的WAIT就算是一个单词。假设我们已经有所有单词的词库。

容易想到的方法是我们可以从左上角[0,0]开始，用DFS的方法进行搜索；之后再从[0,1]开始，以此类推。因为DFS过程中，每新增一个字母，我们都要去跟词库做一次比较，所以词库如何实现对程序的运行效率有很大的影响。

Untitled

需要一个快速查找有没有某元素的数据结构，我们容易想到哈希表，但是在这个需求里，哈希表不能满足需求。就像上面WAIT的例子，搜索的时候应该是W -> WA -> WAI -> WAIT这样，如果词库使用哈希表实现，只能告诉我们WAIT存在，我们的程序依然要处理所有的序列，因为词库不能告诉我们W开头有没有单词，甚至WAIT之后还有没有单词。所以在找到WAIT之后，搜索也不能停下来，否则就可能漏掉正确答案。

如果词库在搜W的时候告诉我们没有搜下去的必要了，那么我们就可以放弃继续搜索，转而搜索其他序列，大大提高效率。

所以我们需要的词库应该满足下面的需求

快速查询一个字符序列是不是一个单词
快速查询还有没有其他以此字符序列开头的更长的单词了
为节省空间，希望每个单词只存储一份

写成程序，我们的词库接口应该是这个样子

public interface Vocabulary {
    boolean add(String word);
    boolean isPrefix(String prefix);
    boolean contains(String word);
}