【Leetcode算法题】318. 最大单词长度乘积

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]仅包含小写字母,那么判断两个单词不含有公共字母,那么只需要对应的1-26字母位积之和是否大于0即可。

比较简单,代码如下所示:

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
public int maxProduct(String[] words) {
if (words == null || words.length <= 1) {
return 0;
}

int n = words.length;
boolean[][] array = new boolean[n][26];
for (int i = 0; i < n; i++) {
String word = words[i];
for (char ch : word.toCharArray()) {
array[i][ch - 'a'] = true;
}
}

int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
boolean flag = true;
for (int k = 0; k < 26; k++) {
if (array[i][k] && array[j][k]) {
flag = false;
break;
}
}
if (flag) {
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是数组words\textit{words}的长度。需要创建长度为nn的位掩码数组 \textit{masks}masks。

方法二: