java - 用字符串列表搜索输入数字(类似于t9字典)

Question

T9 词典如何工作？它背后的数据结构是什么。例如:有 16 个单词的列表/字典(全部大写)。您将输入数字，相应的输出应该是与字典中的数字匹配的单词。如何在 C/C++/JAVA 中实现它。[如果将任何单词添加到列表中，它也应该支持]

2:A/B/C
3:D/E/F
4:G/H/I
5:J/K/L
6:M/N/O
7:P/Q/R/S
8:T/U/V
9:W/X/Y/Z

LIST{DRAWING,PAINTING,DANCE.....}

输出窗口示例:

Input : 3729464
output : DRAWING

Answer 1

如果简单地直接查找完整的单词就足够了，最好编写一个函数，用相应的数字替换单词的字符:

A,B,C  -> 2
D,E,F  -> 3

等等

然后将该函数应用于所有字典条目并将结果存储为键，但将原始形式存储为哈希表(或类似数据结构)的值。由于每个数字可以代表多个不同的字符，因此可能必须将同一个键映射到多个值。您可以使用字符串列表作为值类型:

entries(3829464)  = [DRAWING]
entries(72468464) = [PAINTING]
entries(843)      = [THE,TIE]

等等。

然后您可以直接根据散列键搜索给定的输入数字序列，并轻松检索所有候选数字作为现成列表。

实际的 T9 函数也支持延续:输入一个数字序列，并检索可能是输入序列的延续的所有字符串。为此，搜索树是一种很好的数据结构。同样，字符转换产生的数字最好用作 trie 的转换标签，字符串的原始形式最好存储在接受状态中。您可能希望在内部节点中存储其他信息，例如在给定节点下的子树中找到的接受状态总数；这将帮助您在 O(1) 时间内决定是开始遍历子树以检索所有后续候选者，还是最好等到用户提供更多输入。