4

在 iOS 中，当您开始输入某人的姓名以发送新的 SMS/iMessage 等时，会弹出一个自动完成列表。

我正在尝试重新创建此搜索算法的工作方式，但它并不像您想象的那么简单。你可以在你的设备上试试看我的意思，但例如，如果我输入“Joh”或“Brow”，那么“John Brown”就会出现。但是输入“ohn”不会显示任何结果。更难的是，输入“Mr Green”将允许“Mr Evan Green”显示......在消息中自己尝试一下，这样可能更容易理解。

有没有一种简单的方法来实现这个自动完成算法？（我有一个包含名称的 NSString 数组，以及一个用于过滤它们的子字符串）。

如果没有简单的方法，你会怎么做？

4

2 回答 2

8

为此，您应该从您的字符串中创建一个Trie 。您还可以使用后缀树（对 TRIE 的改进）或后缀数组（基于后缀树的精简数据结构）。查看此链接以了解使用 Trie 的算法。

查看这个问题，了解这些数据结构之间的区别。

后缀树的想法是找到输入字符串的每个后缀的路径，然后您可以使用树搜索来查找随机字符串是否非常快地匹配输入字符串。

于 2012-07-17T08:14:00.557 回答
0

将名字与姓氏分开。然后，检查任一字符串是否以输入的子字符串开头。这将为您提供第一个描述案例所需的行为。

第二种情况比较困难，实现和描述都比较困难。一种方法是用空格分解键入的字符，以便您拥有一个子字符串数组（“Mr”和“Green”）。然后，执行与之前相同的检查；检查数组中的每个以查看它是否与名字或姓氏的开头匹配。如果是，请将其添加到结果中。

于 2012-07-17T08:06:50.403 回答