最大单词长度乘积

题目

题目来源：力扣（LeetCode

给定一个字符串数组 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
解释: 不存在这样的两个单词。

思路分析

• 先判断两个字符串是否有重复的字母
• 若没有相同的字母，则计算字母的乘积。
• 取最大的长度

如何有效且快速的判断两个字符串是否有重复的字母？

利用位运算。一共 26 个小写字母，而整型数一共 32 位。

我们为每一个字符串使用一个长度为26的二进制数字，每一个二进制数字表示当前字符串中是否出现了这个字母；
如果两个字符串出现了相同的字母，那么这两个字符串对应的二进制数字相与结果不为0。

这里我们让整型数的每一位代表每一个字母 ，然后得到的一个整型数，它的前26位比特位用来表示字母（ 1 代表有这个字母，0 代表没有这个字母）。如 “abc” 使用 ‘111’ 即数字 7代替； “abcf” 使用‘100111’ 即数字39。最后进行数字的与运算。如果哪一位相同则说明存在重复的字母，利用&运算即可。再拿“abc” 和 “abcf” 举例子 ‘111’ 和 ‘100111’ 进行与运算不为零 则说明存在相同的字母。

var maxProduct = function (words) {
    var getCharCodeDiff = function (char) {
        return char.charCodeAt(0) - 'a'.charCodeAt(0);
    };
    // 字符串数组的个数
    var n = words.length,
        // 串的长度
        lens = [],
        // 每一个串，对应一个 int，每一个串的一个字符，对应二进制的一位
        // 比如第一个串ab 对应00011，a对应0001等
        masks = [];
    for (var i = 0; i < n; i++) {
        // 每一个字符串的长度
        var len = words[i].length;
        // 记录每个字符长度，方便后面的乘积运算
        lens.push(len);
        // 记录这个串上面有的字母
        var mask = 0;
        // 把字符串的每一字符记录到 int 的某一位
        for (var j = 0; j < len; j++) {
            // 通过函数或者字符要记录在int的哪一位上，然后通过左移，把这个位标记为1 
            // 然后与原临时进行 |运算，|运算会保留原来是1的是，记录不会丢失，有的话还是有，没有的话就加上
            mask |= 1 << getCharCodeDiff(words[i][j]);
        }
        // 把记录好的tmp保存到数组中，代表一个字符串
        masks.push(mask);
    }
    // 最大长度乘积
    var max = 0;
    // 遍历代表字符串的int数组，与后面的串所代表的int进行判断，没有重复就求乘积
    for (var i = 0; i < n; i++) {
        for (var j = i + 1; j < n; j++) {
            // 映射后进行 & 运算，如果所有位置都没有重复，那么结果会是零
            if ((masks[i] & masks[j]) == 0) {
                // 计算乘积，选择大的
                max = Math.max(max, lens[i] * lens[j]);
            }
        }
    }
    return max;
};