跳转至

剑指 Offer II 005. 单词长度的最大乘积

题目描述

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

 

示例 1:

输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。

示例 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] 仅包含小写字母

 

注意：本题与主站 318 题相同：https://leetcode.cn/problems/maximum-product-of-word-lengths/

解法

方法一：位运算 + 枚举

由于题目限定了字符串中只包含英语的小写字母，因此每个字符串可以用一个 $32$ 位整数表示，该整数的每个二进制位都是 $0$ 或 $1$，分别对应字符串的每个字母是否出现。这样一来，我们判断两个字符串是否含有相同字符，只需要将对应的整数进行按位与运算，即可得到一个新的整数，如果新的整数的二进制表示中的每一位都是 $0$，就说明两个字符串不含有相同的字符。

具体地，我们用一个长度为 $n$ 的整数数组 $mask$ 表示每个字符串对应的整数，其中第 $i$ 个元素 $mask[i]$ 表示字符串 $words[i]$ 对应的整数。对于任意两个下标 $i$ 和 $j$，如果 $mask[i]$ 和 $mask[j]$ 按位与运算的结果为 $0$，就说明 $words[i]$ 和 $words[j]$ 不包含相同字符。由于需要找到长度乘积的最大值，因此我们可以枚举所有的 $0 \leq i \lt j \lt n$，并计算 $words[i]$ 和 $words[j]$ 的长度乘积，最终得到长度乘积的最大值。

时间复杂度 $O(n \times (n + |S|))$，空间复杂度 $O(n)$。其中 $n$ 是数组 $words$ 的长度，而 $|S|$ 是字符串的最大长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maxProduct(self, words: List[str]) -> int:
        mask = [0] * len(words)
        for i, w in enumerate(words):
            for c in w:
                mask[i] |= 1 << (ord(c) - ord("a"))
        ans = 0
        for i, a in enumerate(words):
            for j, b in enumerate(words[i + 1 :], i + 1):
                if (mask[i] & mask[j]) == 0:
                    ans = max(ans, len(a) * len(b))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] mask = new int[n];
        for (int i = 0; i < n; ++i) {
            for (char c : words[i].toCharArray()) {
                mask[i] |= 1 << (c - 'a');
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((mask[i] & mask[j]) == 0) {
                    ans = Math.max(ans, words[i].length() * words[j].length());
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        int mask[n];
        memset(mask, 0, sizeof(mask));
        for (int i = 0; i < n; i++) {
            for (char c : words[i]) {
                mask[i] |= 1 << (c - 'a');
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((mask[i] & mask[j]) == 0) {
                    ans = max(ans, int(words[i].size() * words[j].size()));
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func maxProduct(words []string) (ans int) {
    n := len(words)
    mask := make([]int, n)
    for i, w := range words {
        for _, c := range w {
            mask[i] |= 1 << (c - 'a')
        }
    }
    for i, x := range mask {
        for j := i + 1; j < n; j++ {
            if x&mask[j] == 0 {
                ans = max(ans, len(words[i])*len(words[j]))
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function maxProduct(words: string[]): number {
    const n = words.length;
    const mask: number[] = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        for (const c of words[i]) {
            mask[i] |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
        }
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            if ((mask[i] & mask[j]) === 0) {
                ans = Math.max(ans, words[i].length * words[j].length);
            }
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    func maxProduct(_ words: [String]) -> Int {
        let n = words.count
        var masks = [Int](repeating: 0, count: n)

        for i in 0..<n {
            for c in words[i] {
                masks[i] |= 1 << (c.asciiValue! - Character("a").asciiValue!)
            }
        }

        var maxProduct = 0
        for i in 0..<n {
            for j in i+1..<n {
                if masks[i] & masks[j] == 0 {
                    maxProduct = max(maxProduct, words[i].count * words[j].count)
                }
            }
        }

        return maxProduct
    }
}

评论