data-structures - 使用 trie 实现 t9 字典

Question

在一次技术面试中，我被要求实现 t9 字典。我知道它可以使用尝试来完成，但不知道如何去做。谁能解释一下？
注意：不要因为这个而将其标记为重复，因为它不包含任何解释。

Answer 1

1）建立一个特里（将字典中的所有单词添加到它）。
2）最初，当前节点是树的根。
3）当输入一个新字符时，可以简单地从当前节点到该字符对应的边上的下一个节点（如果无处可去则报错）。
4）要获得k具有给定前缀的所有（或第一个）可能的单词，您可以从当前节点开始以深度优先搜索顺序遍历trie（如果您只需要k第一个单词，您可以在找到单词时停止搜索k） .
5）当整个单词输入完毕并开始一个新单词时，再次移动到词根，并为下一个单词重复步骤3） - 5）。

PS 在构建trie的时候可以标记一个单词（不是单词的前缀，而是整个单词）对应的所有节点，这样在遍历trie的时候就很容易理解是否找到了新单词步骤 4）。