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

Question

如果两个英语单词只包含相同的字母，则它们是相似的。例如，食物和好东西并不相似，但狗和好东西是相似的。（如果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 love volvell lover levo love love 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

我会尽量避免为此使用正则表达式，并会自己检查字母。

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;

  for (String word : arr)
  {
    if (isSimilar(s, word))
    {
      result++;
    }
  }

  System.out.println(result);
}

private static boolean isSimilar(String word, String test)
{
  for (char c : test.toCharArray())
  {
    if (word.indexOf(c) == -1)
    {
      return false;
    }
  }
  return true;
}

虽然目前我上面的例子只返回10？

Answer 2

我建议简化正则表达式，不需要前瞻，简单的“^[love]*$”就可以了。

private static String buildPattern(String s) {
    String pattern = "^[";
    for (int i = 0; i < s.length(); i++) {
        pattern += s.charAt(i);
    }
    pattern += "]*$";
    return pattern;
}

Answer 3

由于只有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);
}