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

Question

问题:

Using pairs of words from a dictionary with no letters in common, find a pair that maximizes the sum of the words' lengths

Example Dictionary: mouse, cow, join, key, dog

dog and key share no letters and have a sum of 3+3 = 6

mouse does not work with cow, join, or dog because they all share the letter 'o'

join and key share no letters and have a sum of 4+3 = 7

我在面试中遇到了这个问题，我想出的解决方案概述如下。我想知道是否有任何方法可以提高效率？我使用了两个 BitSets 来映射两个单词的字母表，并将它们放在一起以查看它们是否包含相同的字母。我认为我的算法复杂度为 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

Answer 1

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

首先 构建一个二维 boolean 数组 D[i][j]。

i - 整数

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

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

在你有了这个二维数组之后，你可以检查每对单词是否有一个共同的字母(你迭代每一对，字典中的每个字母)。如果他们不这样做，您将实现最大金额。