我想实现一个简单的类(在Java中)，该类允许我注册和注销字符串，并根据当前的字符串集自动完成给定的字符串。因此，接口为：

• 无效add(String)
• 无效remove(String)
• 字符串完成(字符串)

就算法和数据结构而言，最好的方法是什么？

解决方案

回答

常用表达。

回答

它必须是某种可以按排序顺序维护的列表。我们还必须编写自己的搜索算法，该算法将为我们提供与搜索模式匹配的列表中第一个元素的索引。然后从该索引进行迭代，直到第一个不匹配的元素，我们便拥有了可能的补全列表。

我会从commons-collections看TreeList。它具有从列表中间快速插入和删除的时间，我们将需要该时间来保持排序的顺序。从支持该列表的树中编写搜索功能可能相当容易。

回答

我们所追求的数据结构称为三元搜索树。

在www.javaworld.com/javaworld/jw-02-2001/jw-0216-ternary.html上有一个很棒的JavaWorld示例。

回答

我们应该考虑对数据结构使用PATRICIA trie。在Google上搜索" patricia trie"，我们会发现很多信息...

回答

对于那些偶然发现这个问题的人...

我刚刚在Google Code上发布了服务器端自动完成功能的实现。该项目包括一个可以集成到现有应用程序中的Java库和一个独立的HTTP AJAX自动完成服务器。

我的希望是使人们能够将有效的自动完成功能集成到他们的应用程序中。踢轮胎！

回答

我创建了一个名为Simple AutoComplete的JQuery插件，该插件可让我们在同一页面上根据需要添加许多自动完成功能，并添加带有额外参数的过滤器，并执行回调函数以带来其他参数，例如商品的ID。

参见http://www.idealmind.com.br/projetos/simple-autocomplete-jquery-plugin/