本文旨在讨论使用 Java 的搜索自动完成的低级实现，将Trie在用例中使用数据结构。
这是一个示例TrieNode类：
class TrieNode{ Map<Character,TrieNode> children; boolean isEndOfWord; TrieNode(){ children = new HashMap<>(); isEndOfWord = false; }}请注意，我们在这里使用 Map 来存储 Trie 中特定层级的所有字符。如果问题是按字母顺序返回结果，那么我们别无选择，只能使用 TreeMap，能确保顺序，但会在插入和搜索时耗费时间，因为 TreeMap 查找/插入将耗费 log(n) 时间。
在本文中，我们假设可以按任意顺序返回结果，以使事情变得简单。
另外，假设我们有来自后台的缓存响应。我们可以将其作为自动完成任务的单词来源。让这个输入是单词，假设我们正在搜索一个单词 searchWord 。因此，方法定义可归结为以下内容：
public List<String> suggestedWords(String[] words, String searchWord) { for (String word: words) { insert(word); // insert to Trie } return search(searchWord); // search in Trie and return results}方法 insert(String word) 可以在 Trie 中插入单词。以下是该方法的示例实现。请注意，我们需要将最后一个 TrieNode 的 isEndOfWord 标志设置为 true，表示单词的最后一个字符。
private void insert(String word) { int len = word.length(); TrieNode current = this.root; // member variable pointing to the root of TrieNode for (int i = 0; i < len; i++) { TrieNode node = current.children.get(word.charAt(i)); if (node == null) { node = new TrieNode(); current.children.put(word.charAt(i), node); } current = node; } current.isEndOfWord = true;}Trie 可以预先填充，也可以在应用服务器中设置。
因此，实时查询只需直接调用 search(searchWord)。在插入一堆单词后，它看起来就像下面这样（例如：apple, ape, god, good）：
现在到了主要部分，即搜索自动完成。首先，我们需要实现前缀搜索。我们应该能够在 Trie 中搜索前缀。如果找到匹配，我们就需要搜索该特定 TrieNode 中的完整单词。实时应用将返回 k 个结果，而不是所有单词。为了实现实时性能，返回 k 个单词是合理的。以下是前缀搜索的实现：
private TrieNode startsWith(String prefix) { int len = prefix.length(); TrieNode current = this.root; for (int i = 0; i < len; i++) { TrieNode node = current.children.get(prefix.charAt(i)); if (node == null) { return null; } current = node; } return current;}如果在 Trie 中没有找到前缀，我们将返回 null，否则我们将返回 TrieNode 作为主要搜索的起点。在最坏的情况下，前缀搜索只需要 O(n) 时间。下面，让我用迄今为止定义的所有方法重写搜索函数：
private List<String> search(String searchWord) { List<String> result = new ArrayList <> (); TrieNode current = this.root; int len = searchWord.length(); current = startsWith(searchWord); if (current != null) { List<String> list = new ArrayList <> (); StringBuilder sb = new StringBuilder(searchWord); // backtrack(list, current, sb, k); yet to implement. result.addAll(list); } return result;}请注意，searchWord 可能是一个完整的词，也可能不是。但这并不重要，我们会返回 searchWord 的所有完整单词。我已经对上述代码进行了注释，这些代码还有待讨论/实现。我们可以使用回溯法从前缀 TrieNode 开始遍历所有后续 TrieNode，直到找到一个完整的单词。请参考下面的实现：
private void backtrack(List<String> list, TrieNode current, StringBuilder sb, int k) { if (list.size() == k) { return; } if (current.isEndOfWord) { list.add(sb.toString()); } for (Map.Entry<Character,TrieNode> entry: current.children.entrySet()) { sb.append(entry.getKey()); backtrack(list, entry.getValue(), sb); sb.setLength(sb.length() - 1); }}当最多收集到 k 个单词时，我们就停止回溯 Trie。最重要的是，我们会借助 isEndOfWord 标志来收集单词。StringBuilder 的使用在此不言自明。一旦完成回溯，结果将包含所有完整的单词。现在，如果我们需要返回短语列表而不是单词列表，也可以采用同样的解决方案。这里的单词是短语的同义词，所以并不重要。
您可以在实际的编码面试中快速完成编码，改进的空间是无限的！编码快乐
