0

给定一部只有数字键盘的手机，我们需要以一种可以快速搜索的方式存储联系人。

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

我在一次采访中被问到这个问题，我建议创建一个 trie。对于地址簿中的每个名字，我建议在 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 技术中T9 类型字典背后的数据结构

4

2 回答 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 更精简、更简单的数据结构。

于 2013-01-29T03:29:35.350 回答
0

您可以根据字母构建一棵树，但它需要是三个值，左，右，电话号码列表

所以用你的例子：

                              root node

               b  (left node)                   m  (right node)
               o                                a
               b (number)             v                   t
               y (number)

然后，您可以沿着节点向下走以显示自动完成建议，例如，如果需要bob，boby您可以显示两个名称。

更新

今天早上我想了一下，这篇论文可能会为如何解决这个问题提供一些新的想法，因为它使用三叉树对字符串进行排序。

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

但是，如果我的示例中的节点有 5 个值，那么您有：

  1. 左节点
  2. 右节点
  3. 下节点
  4. 当前信
  5. 适用的电话号码列表

然后向左或向右搜索，直到在该位置找到正确的字母，然后向下，然后向左或向右，直到找到下一个。

这样，每个节点中的每个字母都没有 26 个指针，所以这棵树会很稀疏，但很可能是不平衡的。平衡它将是一个不同的问题。

于 2013-01-30T01:54:05.667 回答