有趣的算法我想听取社区的意见。我希望遍历 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 大得多?
最佳答案
如果你真的想避免 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
关于java - 数组中以字符串开头的单词,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17661366/