java - 使用字典中没有共同字母的单词对，找到使单词长度总和最大化的一对

问题:



我在一次采访中遇到了这个问题，我想出的解决方案概述如下。我想知道是否有任何方法可以提高效率？我使用了两个 BitSets 来映射两个单词的字母表，然后将它们 AND 放在一起，看看它们是否包含相同的字母。我认为我的算法的复杂度是 o(n!)，这是低效的，有没有更好的方法来优化我的算法？

public static void maximumSum (String[] dictionary) {
    // ascii of a = 97
    BitSet word1 = new BitSet(26);
    BitSet word2 = new BitSet(26);

    String maxWord1 = "";
    String maxWord2 = "";
    int maxSum = -1;

    for(int i = 0; i<dictionary.length; i++) {
        for(int j = i+1; j<dictionary.length; j++) {
            String s1 = dictionary[i];
            String s2 = dictionary[j];
            for(int k = 0; k<s1.length(); k++) {
                word1.set(s1.charAt(k)-97);
            }
            for(int k = 0; k<s2.length(); k++) {
                word2.set(s2.charAt(k)-97);
            }
            word1.and(word2);
            if(word1.cardinality() == 0) {
                if(maxSum < s1.length()+s2.length()) {
                    maxWord1 = s1;
                    maxWord2 = s2;
                    maxSum = s1.length()+s2.length();
                }
            }
            word1.clear();
            word2.clear();
        }
    }
    if(maxSum == -1)
        System.out.println("All the words have letters in common.");
    else
        System.out.println("'"+maxWord1+"' and '"+maxWord2+"'
        have a maximum sum of "+maxSum);
}

public static void main(String[] args) {
    String[] dictionary = {"mouse", "cow", "join", "key", "dog"};
    maximumSum(dictionary);
}

输出:

'join' and 'key' have a maximum sum of 7

最佳答案

您可以在 O(N^2 * 26) 中执行此操作(26 表示字典中的字符数，可能是英文字母)。

第一个
构建一个二维 boolean 数组，D[i][j]。

i - 整数

j - 字符 从 'a' 到 'z'(您可以使用 ASCII 代码代替字符)

如果索引 i 处的单词包含字母 j，则 D[i][j] = 1，否则 D[i][j] = 0；

有了这个 2D 数组后，您可以检查每对单词是否有一个共同的字母(您对字典中的每一对、每个字母都进行迭代)。如果他们不这样做，您将实现最大总和。

关于java - 使用字典中没有共同字母的单词对，找到使单词长度总和最大化的一对，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29734387/