java - 如何找到至少一次包含所有给定字符的任何单词

Question

我使用这段代码

                   while((dictionaryWord = br_.readLine()) != null) 
            {
                if(dictionaryWord.matches("^"+word.replace("*" , "." )+"$"))
                {   
                    incrementCounter();
                    System.out.println(dictionaryWord);
                }
            }

预期目标：word = dgo

输出：dog、god、dogma megalogdon 等......

Answer 1

public static void main(String[] args) {
  final BitSet reqChars = new BitSet(26);
  for (char c : "dog".toCharArray()) reqChars.set(Character.toLowerCase(c) - 'a');
  for (String w : new String[] {"god", "dogma", "megalogdon", "dorm"})
    if (hasAllChars(w, reqChars)) System.out.println(w);
}

public static boolean hasAllChars(String in, BitSet req) {
  req = (BitSet)req.clone();
  for (char c : in.toCharArray()) {
    req.set(Character.toLowerCase(c) - 'a', false);
    if (req.isEmpty()) return true;
  }
  return false;
}

Answer 2

您可以在 中构建Set<Character>所有字符word，然后对其进行迭代。如果一个字符不在 中dictionaryWord，dictionaryWord则不适合。仅当全部出现时 - 打印dictionaryWord

    String word = "dog";
    String  dictionaryWord;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    while((dictionaryWord = br.readLine()) != null)  {
        Set<Character> chars = new HashSet<Character>();
        for (char c : word.toCharArray()) {
            chars.add(c);
        }
        boolean match = true;
        for (Character c : chars) {
            String s = "" + c;
            if (!dictionaryWord.contains(s)) {
                match = false;
                break;
            }
        }
        if (match == true) 
            System.out.println(dictionaryWord);
    }

在上面的代码中，当然可以将集合创建移出while循环。

更有效的解决方案可能是也创建一个Setfrom dictionaryWord，然后检查两个集合的交集是否与表示 的集合相同word。
这将是：

    String word = "dog";
    Set<Character> set1 = new HashSet();
    for (char c : word.toCharArray()) {
        set1.add(c);
    }
    String  dictionaryWord;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    while((dictionaryWord = br.readLine()) != null)  {
        Set<Character> set2 = new HashSet();
        for (char c : dictionaryWord.toCharArray()) {
            set2.add(c);
        }           Set<String> intersection = new HashSet(CollectionUtils.intersection(set1, set2));
        if (set1.equals(intersection)) {
            System.out.println(dictionaryWord);
        } else System.out.println("bad");
    }

CollectionUtils.intersection()从 apache commons使用

Answer 3

public static boolean containsAllCharacters(String word, Set<String> characters){
    int i = 0;
    int wordLength = word.getLength();
    while (i <= wordLength && characters.contains(word.get(i++)){}
    return i==wordLength;
}

Answer 4

实际上，这个问题最有趣的部分是如何避免查看字典中的每个单词（尽管原始代码类型掩盖了这一点）。一个可能有趣的答案是：

1. 按出现频率制作一个包含 26 个字符的表格。
2. 查找每个字符，找到出现频率最低的字符。
3. 然后对包含该字符的单词进行匹配。

当然，这是假设单个匹配比正则表达式便宜。

关于这个主题的很棒的维基百科页面在这里。在这种情况下，差异可能不会很大，但例如在 e 和 x 的情况下，差异会很大。