跳到主要内容

318.最大单词长度乘积

· 阅读需 5 分钟

1、题干​

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

 

示例 1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。

示例 2：

输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4 
解释：这两个单词为 "ab", "cd"。

示例 3：

输入：words = ["a","aa","aaa","aaaa"]
输出：0 
解释：不存在这样的两个单词。

 

提示：

  • 2 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • words[i] 仅包含小写字母

思路​

  • 暴力解法：

    • 暴力解法是做个嵌套循环遍历所有words，判断两个word是否有相同字母需要再遍历word中的字符
    • 按暴力解法估算时间复杂度大概是O(n^3)，n取1000的话，超时基本没跑了
    • 实际上2层嵌套循环基本无法避免，也就是说时间复杂度至少是O(n^2)，那就想办法再减少一层遍历

  • 第1层优化-字典：

    • 题目中说到 每个单词只包含小写字母，通常会想到把单词转换成以字母为key的哈希表或者数组字典来做优化
    • 根据题意，使用数组表示单词时，只要将字母对应ASCII码顺序作为索引，值为bool类型即可
    • 举个例子，单词abc可以表示为[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1]，单词a可以表示为[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
    • 判断两个单词是否包含相同字母需要做一次遍历，由于数组长度恒定为26，因此时间复杂度为常数
    • 至此，时间复杂度已经可以达到O(n^2)

  • 第2层优化-位运算：

    • 实际上，如果用二进制整数来表示单词会更简洁 abc可以表示为0b111，a可以表示为0b1
    • 而且判断两个单词是否有相同字母只需要做一次&运算而不需要遍历数组，&运算结果为0则表示没有相同字母
    • 这个优化不能减少时间复杂度，但是可以减少执行时间

  • 解题步骤：

    • 1、遍历words，将words中的单词转换为长度为2的数组[bit,word.length]，数组两个元素分别表示单词的二进制和单词的长度
    • 2、再次遍历words，把当前单词与剩余单词做匹配，如果不存在相同单词，则计算长度乘积
    • 3、返回长度乘积的最大值，具体代码如下

  • 进一步优化：

    • 题解中说到单词转成二进制之后可能会相等，因此可以用哈希表做进一步优化（答题的时候没想到，另外考虑到单词组合问题，26个字母组成1000个单词，最坏情况下转成二进制之后可能没有相等的情况，因此就不写了）
    • 答题的时候发现运算次数达到一定量级之后，位运算的速度比乘方运算更快些（属于自己挖坑了，这里耗时差距能达到10+倍，具体参考附录）

代码​

var maxProduct = function (words) {
    const CODEA = 'a'.charCodeAt(0);
    for (let i = 0; i < words.length; i++) {
        let bit = 0;
        for (let j = 0; j < words[i].length; j++) {
            const p = words[i].charCodeAt(j) - CODEA;
            bit = bit | (1 << p);
        }
        words[i] = [bit, words[i].length];
    }

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

    return res;
};

附录​

const K = 1e6;
const MOD = 10;

console.time('乘方');
let n = 0;
for (let i = 0; i < K; i++) {
  n = n | (2 ** (i % MOD));
}
console.timeEnd('乘方');

console.time('位运算');
n = 0;
for (let i = 0; i < K; i++) {
  n = n | (1 << (i % MOD));
}
console.timeEnd('位运算');
// 浏览器下执行结果
// 乘方: 78.853759765625 ms
// 位运算: 6.093994140625 ms