java - 数组中以字符串开头的单词

Question

有趣的算法我想听取社区的意见。我希望遍历 Sorted ArrayList<String>如果数组中存在以特定字符开头的字符串，则为 boolean 结果。

例。数组 {"he", "help", "helpless", hope"}

search character = h 
Result: true
search character = he
Result: true
search character = hea
Result: false

现在我的第一印象是我应该将二进制搜索与正则表达式结合起来，但如果我离得远，请告诉我。虽然 trie 将是最好的实现，但我需要一个最小化堆内存的解决方案(在 android 上开发)，因为这个数组实际上将包含 ~10,000-20,000 个条目(单词)。

我有一个包含约 200,000 个单词的数据库。我正在获取一个以固定字母(在我的示例中为 h)开头的子集，它将包含约 20,000 个条目并将它们插入到数组中。然后我使用这个子集执行 ~100-1,000 次查找/包含。我的想法是增加性能时间(而不是数据库查询)，同时尽量减少对内存的命中(数组而不是 trie 树)

也许 DAWG 会优化查找，但我不确定此结构的大小要求是否会比 ArrayList 大得多？

Answer 1

如果你真的想避免 trie ，这应该符合您的需求:

NavigableSet<String> tree = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
tree.addAll(Arrays.asList("he", "help", "helpless", "hope"));
String[] queries = {"h", "he", "hea"};
for (String query : queries) {
    String higher = tree.ceiling(query);
    System.out.println(query + ": " + higher.startsWith(query));
}

打印

h: true
he: true
hea: false