检查字符串中是否存在字符集 - 改进

Question

如果两个英语单词只包含相同的字母，则它们是相似的。例如，food 和 good 不相似，但 dog 和 good 相似。（如果 A 与 B 相似，则 A 中的所有字母都包含在 B 中，B 中的所有字母都包含在 A 中。）

给定一个单词 W 和一个单词列表 L，找到 L 中与 W 相似的所有单词。将单词计数打印到标准输出。

例子：

输入（标准输入）：

love
velo low vole lovee volvell lowly lower lover levo loved love lovee lowe lowes lovey lowan lowa evolve loves volvelle lowed love

输出（标准输出）：

14

解释：

L中与love相近的词是 velo vole lovee volvell lover  levo loved love lovee lovey evolve loves volvelle love

最多14.

所以我目前的解决方案如下：

public static void main(String[] args) {

    String[] arr = new String[]{"velo", "low", "vole", "lovee", "volvell", "lowly", "lower", "lover", "levo", "loved", "love",

            "lovee", "lowe", "lowes", "lovey", "lowan", "lowa", "evolve", "loves", "volvelle", "lowed", "love"};

    String s = "love";

    int result = 0;

    Pattern p = Pattern.compile(buildPattern(s));

    for (String val : arr) {

        if (p.matcher(val).find()) result++;

    }

    System.out.println(result);

}

private static String buildPattern(String s) {

    String pattern = "^";

    for (int i = 0; i < s.length(); i++) {

        pattern += "(?=.*" + s.charAt(i) + ")";

    }

    return pattern;

}

我想知道我的简单代码是否有任何改进。

Aho-Corasick 是否适用解决方案？

Answer 1

由于只有 26 个字母，而 an 中有 32 位int，因此 anint足以容纳有关单词中出现的字母的所有信息：static int getFingerprint(String s){&nbsp; &nbsp; int result=0;&nbsp; &nbsp; for (int i = s.length()-1; i>=0; --i) {&nbsp; &nbsp; &nbsp; &nbsp; char c = s.charAt(i);&nbsp; &nbsp; &nbsp; &nbsp; if (c>='a' && c<='z')&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result |= 1<<(int)(c-'a');&nbsp; &nbsp; &nbsp; &nbsp; else if (c>='A' && c<='Z')&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result |= 1<<(int)(c-'A');&nbsp; &nbsp; }&nbsp; &nbsp; return result;}public static void main(String[] args) {&nbsp; &nbsp; String[] arr = new String[]{"velo", "low", "vole", "lovee", "volvell", "lowly", "lower", "lover", "levo", "loved", "love",&nbsp; &nbsp; &nbsp; &nbsp; "lovee", "lowe", "lowes", "lovey", "lowan", "lowa", "evolve", "loves", "volvelle", "lowed", "love"};&nbsp; &nbsp; String s = "love";&nbsp; &nbsp; int fingerprint = getFingerprint(s);&nbsp; &nbsp; int matches = 0;&nbsp; &nbsp; for (String item : arr) {&nbsp; &nbsp; &nbsp; &nbsp; if (getFingerprint(item)==fingerprint)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++matches;&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println(matches);}

Answer 2

我建议简化正则表达式，不需要前瞻，简单的“^[love]*$”就可以了。private static String buildPattern(String s) {&nbsp; &nbsp; String pattern = "^[";&nbsp; &nbsp; for (int i = 0; i < s.length(); i++) {&nbsp; &nbsp; &nbsp; &nbsp; pattern += s.charAt(i);&nbsp; &nbsp; }&nbsp; &nbsp; pattern += "]*$";&nbsp; &nbsp; return pattern;}

Answer 3

数 10 应该成功！String[] arr = new String[] { "velo", "low", "vole", "lovee",&nbsp; &nbsp; &nbsp; &nbsp; "volvell", "lowly", "lower", "lover", "levo", "loved", "love",&nbsp; &nbsp; &nbsp; &nbsp; "lovee", "lowe", "lowes", "lovey", "lowan", "lowa", "evolve",&nbsp; &nbsp; &nbsp; &nbsp; "loves", "volvelle", "lowed", "love" };String s = "love";Predicate<Character> p = x -> s.indexOf(x) > -1 ? true : false;List<String> asList = Arrays.asList(arr);asList.stream().forEach(x -> {&nbsp; &nbsp; List<Character> chars = new ArrayList<>();&nbsp; &nbsp; for (int i = 0; i < x.length(); i++) {&nbsp; &nbsp; &nbsp; &nbsp; chars.add(x.charAt(i));&nbsp; &nbsp; }&nbsp; &nbsp; boolean anyMatch = chars.stream().allMatch(p);&nbsp; &nbsp; if (anyMatch)&nbsp; &nbsp; &nbsp; &nbsp; count++;});System.out.println(count);

Answer 4

public static void main(String[] args) {&nbsp; &nbsp; String[] arr = new String[]{"velo", "low", "vole", "lovee", "volvell", "lowly", "lower", "lover", "levo", "loved", "love",&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; "lovee", "lowe", "lowes", "lovey", "lowan", "lowa", "evolve", "loves", "volvelle", "lowed", "love"};&nbsp; &nbsp; String s = "love";&nbsp; &nbsp; Set<Character> searchWordCharacters = getDistinctCharacters(s);&nbsp; &nbsp; long result = Stream.of(arr)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .map(Scratch::getDistinctCharacters)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .filter(wordCharacters -> wordCharacters.size() == searchWordCharacters.size())&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .filter(wordCharacters -> wordCharacters.containsAll(searchWordCharacters))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .peek(System.out::println)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .count();&nbsp; &nbsp; System.out.println(result);}private static Set<Character> getDistinctCharacters(String word) {&nbsp; &nbsp; return word.chars()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .mapToObj(i -> (char) i)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .collect(Collectors.toSet());}结果：10

Answer 5

我只计算了 10 个应该成功的，无论是在我的实施中还是在我手动检查时。很简单，就是比较每个单词中的字母集合是否相等public static void main(String... args){&nbsp; &nbsp; String word = "love";&nbsp; &nbsp; List<String> strs = Arrays.asList(&nbsp; &nbsp; &nbsp; &nbsp; "velo", "low", "vole", "lovee", "volvell", "lowly", "lower", "lover", "levo", "loved", "love",&nbsp; &nbsp; &nbsp; &nbsp; "lovee", "lowe", "lowes", "lovey", "lowan", "lowa", "evolve", "loves", "volvelle", "lowed", "love"&nbsp; &nbsp; );&nbsp; &nbsp; System.out.println(&nbsp; &nbsp; &nbsp; &nbsp; strs.stream()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;.filter(str -> chars(word).equals(chars(str)))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;.count()&nbsp; &nbsp; );}private static Set<Character> chars(String word){&nbsp; &nbsp; return word.chars()&nbsp; &nbsp; &nbsp; &nbsp; .mapToObj(ch -> (char) ch)&nbsp; &nbsp; &nbsp; &nbsp; .collect(Collectors.toSet());}