本文主要是介绍318最大单词长度乘积（位运算），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、题目描述
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
2、示例
输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。
输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4
解释: 这两个单词为 "ab", "cd"。
3、题解
基本思想：位运算，用一个32位int表示一个word中出现的字母，用int32位替代上面的vector<int>(26,0)，这样空间复杂度从O(n*26)减小到O(n)，并且判断两个字符串是否有共同字母可以通过(counts[i]&counts[j])==0。
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<iterator>
using namespace std;
class Solution {
public:int maxProduct(vector<string>& words) {//基本思想：建立起counts二维数组对words每个字符串中的字符计数，然后通过双重循环遍历words判断每个字符串与后面字符串是否存在共同字母int res=0;if(words.size()==0) return res;vector<vector<int>> counts(words.size(),vector<int>(26,0));for(int i=0;i<words.size();i++){for(int j=0;j<words[i].size();j++)counts[i][words[i][j]-'a']++;}for(int i=0;i<words.size()-1;i++){for(int j=i+1;j<words.size();j++){bool insectflag=false;for(int k=0;k<words[i].size();k++){if(counts[j][words[i][k]-'a']>0){insectflag=true;break;}}if(insectflag==false)res=max(res,static_cast<int>(words[i].size()*words[j].size()));}}return res;}
};
class Solution1 {
public:int maxProduct(vector<string>& words) {//优化：用一个32位int表示一个word中出现的字母，用int32位替代上面的vector<int>(26,0)，这样空间复杂度从O(n*26)减小到O(n)，//并且判断两个字符串是否有共同字母可以通过(counts[i]&counts[j])==0int res=0;if(words.size()==0) return res;vector<int> counts(words.size(),0);for(int i=0;i<words.size();i++){for(int j=0;j<words[i].size();j++)counts[i]|=1<<words[i][j]-'a';}for(int i=0;i<words.size()-1;i++){for(int j=i+1;j<words.size();j++){if((counts[i]&counts[j])==0)res=max(res,static_cast<int>(words[i].size()*words[j].size()));}}return res;}
};
class Solution2 {
public:int maxProduct(vector<string>& words) {//另一种思路，用set_intersection求交集，但是超时int res=0;if(words.size()==0) return res;vector<set<char>> counts(words.size(),set<char>{});for(int i=0;i<words.size();i++){for(int j=0;j<words[i].size();j++)counts[i].insert(words[i][j]);}for(int i=0;i<words.size()-1;i++){for(int j=i+1;j<words.size();j++){set<char> temp;set_intersection(counts[i].begin(),counts[i].end(),counts[j].begin(),counts[j].end(),inserter(temp,temp.begin()));if(temp.size()==0)res=max(res,static_cast<int>(words[i].size()*words[j].size()));}}return res;}
};
int main()
{Solution2 solute;vector<string> words={"abcw","baz","foo","bar","xtfn","abcdef"};int pos=1;cout<<solute.maxProduct(words)<<endl;return 0;
}
这篇关于318最大单词长度乘积（位运算）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
