题目链接：https://s.heyiqi.cc/bp8
题目描述
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
示例 1：
1
2
3
| 输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。
|
示例 2：
1
2
3
| 输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4
解释: 这两个单词为 "ab", "cd"。
|
示例 3：
1
2
3
| 输入: ["a","aa","aaa","aaaa"]
输出: 0
解释: 不存在这样的两个单词。
|
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母
方法一：暴力
每次用哈希表记录每个单词，并在第二个单词中判断有没有出现过。
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 {
public:
int maxProduct(vector<string>& words) {
int n = words.size();
int ans = 0;
for(int i=0;i<n;i++){
unordered_set<char>set;
for(auto x:words[i]) set.insert(x);
for(int j=0;j<n;j++){
if(j==i)continue;
bool flag = true;
for(auto x:words[j]){
if(set.count(x)){
flag=false;
break;
}
}
if(flag) ans = words[i].size()*words[j].size() > ans ? words[i].size()*words[j].size() : ans;
}
}
return ans;
}
};
|
时间复杂度：O(n^2)
空间复杂度：O(n)
方法二：位运算
由于只包含小写字母a-z，使用一个int（32位）来保存出现过的字母，再进行&按位与 操作，如果得到0，则未出现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
int getBitOfWord(string &word){
int ans = 0;
for(const auto &c : word)
ans |= (1<<(c-'a'));
return ans;
}
public:
int maxProduct(vector<string>& words) {
int ans = 0;
for(int i=0;i<words.size();i++)
for(int j=0;j<words.size();j++)
if(!(getBitOfWord(words[i]) & getBitOfWord(words[j])))
ans = words[i].size()*words[j].size() > ans ? words[i].size()*words[j].size() : ans;
return ans;
}
};
|
时间复杂度：O(n^2)
空间复杂度：O(n)
方法三：C库函数 strpbrk()
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int maxProduct(vector<string>& words) {
int ans = 0;
for(int i=0;i<words.size();i++)
for(int j=0;j<words.size();j++)
if(!strpbrk(words[i].c_str(),words[j].c_str()))
ans = words[i].size()*words[j].size() > ans ? words[i].size()*words[j].size() : ans;
return ans;
}
};
|
以下内容来自菜鸟教程：https://s.heyiqi.cc/9w0
C 库函数 - strpbrk()
描述
C 库函数 char *strpbrk(const char *str1, const char *str2) 检索字符串 str1 中第一个匹配字符串 str2 中字符的字符，不包含空结束字符。也就是说，依次检验字符串 str1 中的字符，当被检验字符在字符串 str2 中也包含时，则停止检验，并返回该字符位置。
声明
char *strpbrk(const char *str1, const char *str2)
参数
- str1 – 要被检索的 C 字符串。
- str2 – 该字符串包含了要在 str1 中进行匹配的字符列表。
返回值
该函数返回 str1 中第一个匹配字符串 str2 中字符的字符数，如果未找到字符则返回 NULL。
实例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <stdio.h>
#include <string.h>
int main ()
{
const char str1[] = "abcde2fghi3jk4l";
const char str2[] = "34";
char *ret;
ret = strpbrk(str1, str2);
if(ret)
{
printf("第一个匹配的字符是： %c\n", *ret);
}
else
{
printf("未找到字符");
}
return(0);
}
|