[LeetCode] 318. Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16 
Explanation: The two words can be "abcw", "xtfn".

Example 2:

Input: ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4 
Explanation: The two words can be "ab", "cd".

Example 3:

Input: ["a","aa","aaa","aaaa"]
Output: 0 
Explanation: No such pair of words.

Constraints:

• 0 <= words.length <= 10^3
• 0 <= words[i].length <= 10^3
• words[i] consists only of lowercase English letters.

最大单词长度乘积。题意是在一个装着单词的数组里面，找出两个互相之间没有重复字母的单词，比如A和B（但是某一个单词自身可以有重复字母，比如foo, test），算出A.length() * B.length()的最大值。

首先这个帖子可以帮助复习Java位运算的各种操作符。

思路是用bitmap。可以参考这个帖子。用bitmap的方式非常巧妙，这道题把涉及位运算的好几个知识点都融合在一起了。既然是判断每两个单词之间有没有重复的字母，那我们将每个单词都转化成一个二进制的数组，来统计每个字母是否出现过。在二进制中，如果你做了类似这样的操作，你会得到这个字母对应的一个ASCII码，最后的- 'a'操作是在比较当前这个字母的ASCII码与小写字母a的ASCII码（97）的差值。

word.charAt(i) - 'a'

Java第8行，得到这个差值之后，用1 << 差值，意思是把1左移这么多位，然后在累加到val中。跑一个例子，如果给的单词是cde，

0000 0001 -> 这是1的二进制写法，我只写出最后8位

words[i].charAt(j) - 'a' => 'c' - 'a' = 2

1 << 2 = 0000 0100

words[i].charAt(j) - 'a' => 'd' - 'a' = 3

1 << 3 = 0000 1000

words[i].charAt(j) - 'a' => 'e' - 'a' = 4

1 << 4 = 0001 0000

然后如上这三个操作都通过位或( | )操作累加到val中，得到0001 1100。这样单词cde的二进制的bitmap就写好了。如果同一个单词中出现了重复字母也没事，因为在相同位置上出现多少个1，最终还是1。这个val数组说白了只是在记录到底出现过哪些字母。接着把val放入bytes数组中，记录下当前单词的bitmap结果。

最后遍历bytes数组，对每两个单词的bitmap做位与(&)操作，如果有任何一个位置上两个单词的bitmap都是1，这一位才是1，说明两个单词有相同字母。如果两个单词的位与(&)操作结果为0，则证明两者互相之间没有相同字母，则可以试图计算两个单词长度的乘积。

时间O(n^2) - n是单词个数

空间O(n) - 一个32位的数组

Java实现

class Solution {
    public int maxProduct(String[] words) {
        int res = 0;
        int[] bytes = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int val = 0;
            for (int j = 0; j < words[i].length(); j++) {
                val |= 1 << (words[i].charAt(j) - 'a');
            }
            bytes[i] = val;
        }
        for (int i = 0; i < bytes.length; i++) {
            for (int j = i + 1; j < bytes.length; j++) {
                if ((bytes[i] & bytes[j]) == 0) {
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {string[]} words
 * @return {number}
 */
var maxProduct = function(words) {
    var max = 0;
    var holder = new Array(words.length).fill(0);

    for (var i = 0; i < words.length; i++) {
        for (var j = 0; j < words[i].length; j++) {
            holder[i] |= 1 << (words[i].charCodeAt(j) - 97);
        }
    }

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

    return max;
};

LeetCode 题目总结