T9类型字典背后的数据结构 [英] Data structure behind T9 type of dictionary

问题描述

T9 词典如何工作?它背后的数据结构是什么.如果我们输入4663"，我们会在按下按钮时得到good"，然后我们得到gone"然后home"等等......

How does a T9 dictionary work? What is the data structure behind it. If we type '4663' we get 'good' when we press down button we get 'gone' then 'home' etc...

如果用户输入 46，那么它应该显示go"，按下箭头时应该显示gone"等...

If the user types in 46 then it should show 'go' and when pressed down arrow should show 'gone' etc...

推荐答案

可以通过多种方式实现，其中之一是 尝试.路径用数字表示，节点指向单词集合.

It can be implemented in several ways, one of them is Trie. The route is represented by the digits and the nodes point to collection of words.

也可以使用嵌套哈希表来实现，哈希表的关键是一个字母，在每个数字上，算法计算所有可能的路线(O(3^n) 路线).

It can be implemented using nested hash tables as well, the key of the hash table is a letter and on every digit the algorithm calculates all possible routes (O(3^n) routes).

这篇关于T9类型字典背后的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！