使用trie实现t9字典

Question

在一次技术面试中，我被要求实现t9字典。我知道这可以通过尝试来完成，但我不知道如何去做。有谁能解释一下吗？

注意:不要因为this而将其标记为重复，因为它不包含任何解释。

Answer 1

1)构建一个trie(将字典中的所有单词添加到其中)。

2)最初，当前节点是trie的根。

3)当输入一个新字符时，您可以通过与该字符对应的边从当前节点转到下一个节点(如果无处可去，则报告错误)。

4)要获得具有给定前缀的所有(或k优先)可能的单词，您可以从当前节点开始按深度优先搜索顺序遍历trie (如果您只需要k优先单词，则可以在找到k单词时停止搜索)。

5)当输入整个单词并开始一个新单词时，再次移动到词根，并为下一个单词重复步骤3) -5)。

P.S当构建trie时，可以标记与单词(不是单词的前缀，而是整个单词)相对应的所有节点，以便在步骤4中遍历trie时很容易了解是否找到了新词。