java - Java：检查字符串是否在单词列表中的最有效方法

Question

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

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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;
            }
        }
    }

Answer 4

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

Answer 5

创建一个HashSet字符串为

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

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

Answer 6

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

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

Answer 7

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

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

这比contains().

Answer 8

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

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