如何实现T9字典？

Question

我们如何实现一个在手机上使用的字典(当我们在手机上输入一个消息时使用它)？它显示了可以用输入的字符形成的单词列表。

示例：

4663可以是好的，走了，回家了。

467它显示建议的词是重要的。

Answer 1

简单的解决方案是预先计算单词并构建一个trie树()，其中包含节点中的数字，每个叶节点都将有一个链接到一个链接列表/array(或其他一些数据结构)，这些字符串可以使用这些数字形成。

例如，在任何给定的点上，用户键入4663 -> go到上一个节点的所有子节点(示例中的数字3)都不是空，通过各种路径到达叶节点并打印有效的单词。

注意:由于只有digits=10的数量，trie树的大小将是有限的。三值搜索树( TST )也可以用来代替trie树，但是由于只有10位数字，所以我想使用TST不会有多大的优势。

编辑--正如user1168577指出的，使用类似于使用频率的启发式方法，单词可以按该顺序显示。