我有一个字符串数组String[] words
和一个 28000 字的单词列表。
我想检查字符串数组的任何成员是否在 WordList 中(单词列表在文本文件 wordlist.txt 中)
解决此问题的最有效方法是什么?
我有一个字符串数组String[] words
和一个 28000 字的单词列表。
我想检查字符串数组的任何成员是否在 WordList 中(单词列表在文本文件 wordlist.txt 中)
解决此问题的最有效方法是什么?
将字符串直接放入 aHashSet<String>
而不是数组中,并使用 on set 遍历文件contains
以检查内容。您不会改进 O(1) 访问。Strings
如果存在任何重复项,这还将最小化用于存储的内存。
可以试试数组(树)后缀算法,但是需要实现,看这个:
Step1:不要使用字符串数组。而不是使用 HashSet。
Step2:将文件(即wordlist.txt)内容加载到另一个HashSet
第三步:
Set<String> set1 = new HashSet<String>(); //Load the string array into set
Set<String> set2 = new HashSet<String>(); //load the file contents into set
for (String str : set1) {
for (String str2 : set2) {
if (str.equalsIgnoreCase(str2)) {
break;
}
}
}
你可以使用HashSet<String>
or ArrayList<String>
which hascontains
方法。它将检查您的字符串是否已存储。和
之间的区别是 hashset 不允许重复值并且它不会保持顺序,而 arraylist 允许您重复并且它是有序集合。但是 HashSet 比 arraylist 更有效地执行搜索操作。HashSet
ArrayList
创建一个HashSet
字符串为
HashSet<String> wordSet = new HashSet<String>(Arrays.asList(words));
并使用HashSet.contains(Object o)方法检查您要检查的单词是否存在word
。HashSet
word
存储序列化的 HashSet 而不是原始 words.txt。作为运行应用程序的单独步骤。
然后应用程序只需要加载哈希集一次。
HashSet
add()
如果单词已经存在于集合中,则's返回 false。
for (String str : words) {
if (!wordSet.add(str)) {
System.out.println("The word " + str + " is already contained.");
}
}
这比contains()
.
如果您的单词列表可以放入内存,则 HashSet 就足够了。
如果内存大小是一个问题,请使用BloomFilter。虽然布隆过滤器可能给出错误的答案,但您可以调整它发生的概率。