4

我有一个字符串数组String[] words和一个 28000 字的单词列表。

我想检查字符串数组的任何成员是否在 WordList 中（单词列表在文本文件 wordlist.txt 中）

解决此问题的最有效方法是什么？

4

8 回答 8

9

将字符串直接放入 aHashSet<String>而不是数组中，并使用 on set 遍历文件contains以检查内容。您不会改进 O(1) 访问。Strings如果存在任何重复项，这还将最小化用于存储的内存。

于 2013-09-06T12:54:27.163 回答
2

可以试试数组（树）后缀算法，但是需要实现，看这个：

使用后缀树的字符串中的最长回文

于 2013-09-06T13:02:00.743 回答
1

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;
            }
        }
    }
于 2013-09-06T13:03:11.550 回答
0

你可以使用HashSet<String>or ArrayList<String>which hascontains方法。它将检查您的字符串是否已存储。和
之间的区别是 hashset 不允许重复值并且它不会保持顺序，而 arraylist 允许您重复并且它是有序集合。但是 HashSet 比 arraylist 更有效地执行搜索操作。HashSetArrayList

于 2013-09-06T12:57:46.640 回答
0

创建一个HashSet字符串为

HashSet<String> wordSet = new HashSet<String>(Arrays.asList(words));

并使用HashSet.contains(Object o)方法检查您要检查的单词是否存在word。HashSetword

于 2013-09-06T13:03:42.033 回答
0

存储序列化的 HashSet 而不是原始 words.txt。作为运行应用程序的单独步骤。

然后应用程序只需要加载哈希集一次。

于 2013-09-06T13:05:05.183 回答
0

HashSetadd()如果单词已经存在于集合中，则's返回 false。

for (String str : words) {
  if (!wordSet.add(str)) {
    System.out.println("The word " + str + " is already contained.");
  }
}

这比contains().

于 2013-09-06T13:05:51.490 回答
0

如果您的单词列表可以放入内存，则 HashSet 就足够了。

如果内存大小是一个问题，请使用BloomFilter。虽然布隆过滤器可能给出错误的答案，但您可以调整它发生的概率。

于 2014-03-31T09:36:36.857 回答