algorithm - 如何实现 T9 字典？

Question

我们如何实现在移动设备中使用的字典？（当我们在手机中输入消息时使用）。因为它显示了可以用输入的字符组成的单词列表。

例子：

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

467 它显示建议的单词很重要。

Answer 1

一个简单的解决方案是预先计算单词并构建一个在节点中具有数字的特里树，并且每个叶节点都将具有到可以使用这些字符串形成的链表/数组（或其他一些数据结构）的链接位数。

在任何给定点，例如，用户输入了 4663 -> 转到最后一个节点（示例中的数字为 3）的所有非空子节点，通过各种路径到达叶节点并打印有效单词。

注意：由于位数=10 only ，因此三叉树的大小将受到限制。也可以使用三元搜索树 (TST) 代替 trie 树，但在这里，但由于只有 10 个数字，我猜使用 TST 不会有太大的优势。

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