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

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]words[i]仅包含小写字母,那么先统计出每个单词中的字母数量。

之后两层for遍历字符串,枚举两个字符串words[i]words[i]words[j]words[j],然后暴力检验words[i]words[i]words[j]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+n2×26)O(L + n^2 \times 26),其中其中LL 是数组words\textit{words}中的全部单词长度之和,nn是数组words\textit{words}的长度。

  • 空间复杂度:O(26×n)O(26 \times n),其中nn是数组words\textit{words}的长度。

方法二:位运算

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

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

由于单词只包含小写字母,共有2626个小写字母,而intint3232位,因此可以使用位掩码的最低2626位分别表示每个字母是否在这个单词中出现。将\text{a}\text{z}$分别记为第00个字母到第2525个字母,则位掩码的从低到高的第ii位是11当且仅当第ii个字母在这个单词中,其中0i250 \le i \le 25

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

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

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

方法三:位运算优化

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

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

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

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

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

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

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


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. 😉😃💗