题目描述:
给定一个字符串数组 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]
仅包含小写字母
思路:
题目范围给的很小,但是不能超过O(n^3),遍历每一对不同的单词需要两重循环(组合数,N!),也就是O(n^2)的复杂度,那怎么用最少的时间去判断i,j两个字符串有没有相同的元素呢?以下给出两种方法:
1.哈希每个字母是否出现,由于只有小写字母,我们可以开一个二维数组,g[n][26],g[i][j]表示的是第i个字符串里面是否有(j+'a')这个字母。这个数组可以预处理出来,再判断两个字符串是否有相同字母的时候遍历小写字母表就行了,复杂度为O(n*n*26).
2.用位掩码表示字符串中出现的元素。也是我推荐的写法。
什么叫位掩码?
位掩码(Bit mask),也被称为位运算掩码,是计算机中用来表示和操作一组布尔标志(即二进制位)的技术。它通常用一个整数来表示一组标志位,其中每个标志位对应着一个特定的含义或状态。
在位掩码中,每个标志位可以是0或1,分别表示某种状态的开启或关闭。通过位运算,我们可以对这组标志进行灵活的操作,例如设置特定的标志位、清除标志位、判断标志位是否开启等。
位掩码的关键思想是使用位运算符(例如按位与、按位或、按位取反等)来对位进行操作。通过使用不同的位运算符和移位操作,可以对位掩码进行与、或、非、异或等各种操作,从而实现对各个标志位的灵活控制。
mk[i]表示第i个字符串的位掩码。
26个字母嘛,对应26个01序列,第i位的01表示第i位这个字母是否出现。
0000 0000 0000 0000 0000 0000 01 表示的就是这个字符串只出现了a这个字母。
为什么要这么表示呢?
因为这里判断两个字符串是否有相同字母的时候,我们只需要判断(mk[i]&mk[j])是否等于0就可以了。
等于0意味着 每一位出现的字母都不相同,不等于0表示至少有1位是1&1,也就是存在相同的字母。
代码:
int maxProduct(vector<string>& words) {
int sz = words.size();
int mk[1001] = { 0 };
memset(mk, 0, sizeof mk);
for (int i = 0; i < sz; i++) {
for (int j = 0; j < words[i].size(); j++) {
mk[i] |= 1 << (words[i][j] - 'a');
}
}
int ans = 0;
for (int i = 0; i < sz; i++) {
for (int j = i + 1; j < sz; j++) {
if ((mk[i] & mk[j]) == 0) {
ans = max(ans, (int)words[i].size() * (int)words[j].size());
}
}
}
return ans;
}
值得注意的是:
mk[i] |= 1 << (word[i][j] - 'a') 根据当前字母的ASCII码值减去字母’a’的ASCII码值,得到一个偏移量(即字母在英语字母表中的位置)。然后通过左移操作 1 << (word[i][j] - 'a') 将二进制数字 1 左移偏移量个位置,得到一个位掩码,再通过按位或操作 mk[i] |= ... 将该位掩码与 mk[i] 相或,将对应位置上的位设置为 1。