一、 场景与目标
在使用 IDE 开发软件时， IDE 会提供一种“智能提示”， 根据所输入的字符列出可能的词组； 在日常Web开发中，根据用户输入进行自动提示和补全，也能很好地改善使用体验。本文实现输入自动提示与补全功能。
输入自动补全功能实际上是“前缀匹配问题”， 即给定一个前缀以及一个单词列表， 找出所有包含该前缀的单词。
本文实现的功能是： 根据用户输入的关键字， 给出与之匹配的 Java 关键字。
二、 算法与设计
最简单直观的方案莫过于直接遍历单词列表， 检测每个单词是否包含前缀， 并返回。这样做的缺点是， 每次都要遍历单词列表， 效率非常低下。 一个更好的思路是， 先构建一个前缀匹配映射 Map>， key 是每一个单词中所包含的前缀， value 是包含该 key 的所有单词列表。 那么， 问题就转化为给定一个单词列表 list， 将其转换为 Map> ， 这里 Word, Prefix, Matcher 均为 String 类型。
一种思路是， 遍历每一个单词包含的每一个前缀， 找出所有包含该前缀的单词。
for word in words
for prefix in word(0,i)
for word in words
if (word.startWith(prefix)) {
result.put(prefix, result.get(prefix).add(word));
}
显然， 其效率是 O(总前缀数*总单词数)， 在单词列表比较大的情况下， 其效率是比较低的。 要想避免这种嵌套
