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

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 个字母，而 int 有 32 位，所以一个 int 足够大，可以容纳一个单词中出现了哪些字母的所有信息:

static int getFingerprint(String s)
{
    int result=0;
    for (int i = s.length()-1; i>=0; --i) {
        char c = s.charAt(i);
        if (c>='a' && c<='z')
            result |= 1<<(int)(c-'a');
        else if (c>='A' && c<='Z')
            result |= 1<<(int)(c-'A');
    }
    return result;
}

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 fingerprint = getFingerprint(s);

    int matches = 0;
    for (String item : arr) {
        if (getFingerprint(item)==fingerprint)
            ++matches;
    }
    System.out.println(matches);
}