[Leetcode][318. 最大单词长度乘积] 3种方法：从暴力状态压缩到位运算优化

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 4.7k 阅读时长 ≈ 4 分钟

By Long Luo

Leetcode 318. 最大单词长度乘积 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
318. 最大单词长度乘积

给定一个字符串数组words，找到length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回0。

示例 1:
输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。

示例 2:
输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。

示例 3:
输入: ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。
 
提示：
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母

方法一：暴力 + 状态压缩

思路与算法：

之前做过类似的题目，而且题目中有明显的提示 \(words[i]\) 仅包含小写字母，那么先统计出每个单词中的字母数量。

之后两层for遍历字符串，枚举两个字符串 \(words[i]\) 和 \(words[j]\)，然后暴力检验 \(words[i]\) 和 \(words[j]\) 是否有公共字母，并更新最大值。

比较简单，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static int maxProduct(String[] words) {
    if (words == null || words.length <= 1) {
        return 0;
    }

    int len = words.length;
    boolean[][] cnt = new boolean[len][26];
    for (int i = 0; i < len; i++) {
        String word = words[i];
        for (char ch : word.toCharArray()) {
            cnt[i][ch - 'a'] = true;
        }
    }

    int ans = 0;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            boolean flag = true;
            for (int k = 0; k < 26; k++) {
                if (cnt[i][k] && cnt[j][k]) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                ans = Math.max(ans, words[i].length() * words[j].length());
            }
        }
    }

    return ans;
}

复杂度分析：

  • 时间复杂度：\(O(L + n^2 \times 26)\)，其中其中 \(L\) 是数组 \(\textit{words}\) 中的全部单词长度之和， \(n\) 是数组 \(\textit{words}\) 的长度。
  • 空间复杂度：\(O(26 \times n)\)，其中 \(n\) 是数组 \(\textit{words}\) 的长度。

方法二：位运算

方法一中判断两个单词是否有公共字母需要进行 \(26\) 次比较，如果可以将其时间复杂度降低到 \(O(1)\)，可以将总时间复杂度降低到 \(O(n^2)\)。

可以使用位运算预处理每个单词，通过位运算操作判断两个单词是否有公共字母。

由于单词只包含小写字母，共有 \(26\) 个小写字母，而 \(int\) 有 \(32\) 位，因此可以使用位掩码的最低 \(26\) 位分别表示每个字母是否在这个单词中出现。将 \(\textit{a}\) 到 \(\textit{z}\) 分别记为第 \(0\) 个字母到第 \(25\) 个字母，则位掩码的从低到高的第 \(i\) 位是 \(1\) 当且仅当第 \(i\) 个字母在这个单词中，其中 \(0 \le i \le 25\)。

用数组 \(\textit{masks}\) 记录每个单词的位掩码表示。计算数组 \(\textit{masks}\) 之后，判断第 \(i\) 个单词和第 \(j\) 个单词是否有公共字母可以通过判断 \(\textit{masks}[i]~\&~\textit{masks}[j]\) 是否等于 \(0\) 实现，当且仅当 \(\textit{masks}[i]~\&~\textit{masks}[j] = 0\) 时第 \(i\) 个单词和第 \(j\) 个单词没有公共字母，此时使用这两个单词的长度乘积更新最大单词长度乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int maxProduct(String[] words) {
    if (words == null || words.length <= 1) {
        return 0;
    }

    int len = words.length;
    int[] masks = new int[len];
    for (int i = 0; i < len; i++) {
        String word = words[i];
        int wordLen = word.length();
        for (int j = 0; j < wordLen; j++) {
            masks[i] |= 1 << (word.charAt(j) - 'a');
        }
    }

    int ans = 0;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if ((masks[i] & masks[j]) == 0) {
                ans = Math.max(ans, words[i].length() * words[j].length());
            }
        }
    }

    return ans;
}

复杂度分析：

  • 时间复杂度：\(O(L + n^2)\)。其中 \(L\) 是数组 \(\textit{words}\) 中的全部单词长度之和，\(n\) 是数组 \(\textit{words}\) 的长度。预处理每个单词的位掩码需要遍历全部单词的全部字母，时间复杂度是 \(O(L)\)，然后需要使用两重循环遍历位掩码数组 \(\textit{masks}\)计算最大单词长度乘积，时间复杂度是 \(O(n^2)\)，因此总时间复杂度是 \(O(L + n^2)\)。

  • 空间复杂度：\(O(n)\)。需要创建长度为 \(n\) 的位掩码数组 \(\textit{masks}\)。

方法三：位运算优化

方法二需要对数组 \(\textit{words}\) 中的每个单词计算位掩码，如果数组 \(\textit{words}\) 中存在由相同的字母组成的不同单词，则会造成不必要的重复计算。例如单词 \(\textit{meet}\) 和 \(\textit{met}\) 包含的字母相同，只是字母的出现次数和单词长度不同，因此这两个单词的位掩码表示也相同。

由于判断两个单词是否有公共字母是通过判断两个单词的位掩码的按位与运算实现，因此在位掩码相同的情况下，单词的长度不会影响是否有公共字母，当两个位掩码的按位与运算等于 \(0\) 时，为了得到最大单词长度乘积，这两个位掩码对应的单词长度应该尽可能大。

根据上述分析可知，如果有多个单词的位掩码相同，则只需要记录该位掩码对应的最大单词长度即可。

可以使用哈希表记录每个位掩码对应的最大单词长度，然后遍历哈希表中的每一对位掩码，如果这一对位掩码的按位与运算等于 \(0\)，则用这一对位掩码对应的长度乘积更新最大单词长度乘积。

由于每个单词的位掩码都不等于 \(0\)，任何一个不等于 \(0\) 的数和自身做按位与运算的结果一定不等于 \(0\)，因此当一对位掩码的按位与运算等于 \(0\) 时，这两个位掩码一定是不同的，对应的单词也一定是不同的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int maxProduct(String[] words) {
    if (words == null || words.length <= 1) {
        return 0;
    }

    int len = words.length;
    Map<Integer, Integer> maskMap = new HashMap<>();
    for (int i = 0; i < len; i++) {
        String word = words[i];
        int wordLen = word.length();
        int mask = 0;
        for (int j = 0; j < wordLen; j++) {
            mask |= 1 << (word.charAt(j) - 'a');
        }
        if (wordLen > maskMap.getOrDefault(mask, 0)) {
            maskMap.put(mask, wordLen);
        }
    }

    int ans = 0;
    Set<Integer> maskSet = maskMap.keySet();
    for (int mask1 : maskSet) {
        int len1 = maskMap.get(mask1);
        for (int mask2 : maskSet) {
            if ((mask1 & mask2) == 0) {
                int len2 = maskMap.get(mask2);
                ans = Math.max(ans, len1 * len2);
            }
        }
    }

    return ans;
}

复杂度分析：

  • 时间复杂度：\(O(L + n^2)\)，其中\(L\)是数组 \(\textit{words}\) 中的全部单词长度之和，\(n\)是数组 \(\textit{words}\) 的长度。预处理每个单词的位掩码并将位掩码对应的最大单词长度存入哈希表需要遍历全部单词的全部字母，时间复杂度是 \(O(L)\)，然后需要使用两重循环遍历哈希表计算最大单词长度乘积，时间复杂度是 \(O(n^2)\)，因此总时间复杂度是 \(O(L + n^2)\)。

  • 空间复杂度：\(O(n)\)，其中 \(n\) 是数组 \(\textit{words}\) 的长度。需要创建哈希表记录每个位掩码对应的最大单词长度，哈希表中的记录数量不会超过 \(n\)。

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗