在一次技术面试中,我被要求实现 t9 字典。我知道它可以使用尝试来完成,但不知道如何去做。谁能解释一下?
注意:不要因为这个而将其标记为重复,因为它不包含任何解释。
问问题
1605 次
1 回答
0
1)建立一个特里(将字典中的所有单词添加到它)。
2)最初,当前节点是树的根。
3)当输入一个新字符时,可以简单地从当前节点到该字符对应的边上的下一个节点(如果无处可去则报错)。
4)要获得k
具有给定前缀的所有(或第一个)可能的单词,您可以从当前节点开始以深度优先搜索顺序遍历trie(如果您只需要k
第一个单词,您可以在找到单词时停止搜索k
) .
5)当整个单词输入完毕并开始一个新单词时,再次移动到词根,并为下一个单词重复步骤3) - 5)。
PS 在构建trie的时候可以标记一个单词(不是单词的前缀,而是整个单词)对应的所有节点,这样在遍历trie的时候就很容易理解是否找到了新单词步骤 4)。
于 2014-08-19T16:34:11.680 回答