搜索手机通讯录-Java 学习之路

鉴于手机只有一个数字键盘，我们需要以一种快速搜索的方式存储联系人 .

用户将打入数字，我们必须在地址簿中显示所有以这些数字对应的字母开头的联系人 .

我在接受采访时被问到这个问题，我建议创建一个特里 . 对于地址簿中的每个名称，我建议将相应的号码添加到trie中 .

因此，如果地址簿有以下联系人：

bob
boby
mat 
mav

我会使用相应的数字创建尝试 . 在这种情况下，trie将包含：

262     (At the 2nd node 2, keep a pointer to bob)
2629    (At the node 9, keep a pointer to boby)
628     (At the node 8, keep 2 pointers, one to each of mat & mav)

还有更好的方法吗？

更新：此trie用于此处描述的T9技术Data structure behind T9 type of dictionary

2 回答

0
我怀疑大多数名字在前几个字符中区分自己（例如，在你的列表中有“Theodore”，“Theodor”，“Theodora”将构成一个遥远的异常值） .

在此基础上，您可以使用比trie更简单的东西，即哈希表映射匹配条目列表的前缀（一旦前缀唯一地确定列表中的名称，您不需要更进一步） .

例如，给定 {bob, bobby, matt, mads, zed} 您将拥有哈希表
```
"b" --> [bob, bobby]
"bo" --> [bob, bobby]
"bob" --> [bob, bobby]
"bobb" --> [bobby]
"m" --> [matt, mads]
"ma" --> [matt, mads]
"mat" --> [matt]
"mad" --> [mads]
"z" --> [zed]
```
注意，“非区分”前缀（例如，“b”，“bo”，“bob”）可以共享它们的值列表 .

如果平均公共前缀是k个字符，那么您的开销是k个哈希表条目的因子 . 如果k很小，我怀疑，那么你最终会得到比trie更简洁，更简单的数据结构 .
回复于 2024-04-20T01:29:02+08:00
0
您可以根据字母构建一个树，但它需要三个值，左，右，电话号码列表

以你的例子为例：
```
root node

               b  (left node)                   m  (right node)
               o                                a
               b (number)             v                   t
               y (number)
```
然后，您可以向下走节点以显示自动完成建议，因为在 bob 和 boby 的情况下，如果需要，您可以显示两个名称 .

UPDATE

我今天早上想了一下，本文可能会对如何处理这个问题给出一些新的想法，因为它使用三元树来排序字符串 .

http://www.cs.tufts.edu/~nr/comp150fp/archive/bob-sedgewick/fast-strings.pdf

但是，如果我的示例中的节点有5个值，那么您有：
- 左侧节点
- 右侧节点
- down节点
- 目前的信
- 适用的电话号码列表
然后向左或向右搜索，直到找到该位置的正确字母，然后向下，向左或向右，直到找到下一个字母 .

这样，每个节点中的每个字母都没有26个指针，因此这个树很稀疏，但很可能是不 balancer 的 . balancer 它将是一个不同的问题 .
回复于 2024-04-20T01:29:02+08:00

搜索手机通讯录

2 回答

相关问题