先放题目:
Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0. Example 1: Given [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”] Return 16 The two words can be “abcw”, “xtfn”. Example 2: Given [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”] Return 4 The two words can be “ab”, “cd”. Example 3: Given [“a”, “aa”, “aaa”, “aaaa”] Return 0 No such pair of words.
现附上自己的time limit exceed解法
class Solution { public: int maxProduct(vector<string>& words) { if(words.size()==0) return 0; vector<int> Max_len; for(int i=0;i<words.size();i++) sort(words[i].begin(),words[i].end()); for(int i=0;i<words.size();i++) { vector<int> m; for(int j=0;j<words.size();j++) { char int_sec[100000]; if(j==i) continue; char *int_sec_end=set_intersection(words[i].begin(),words[i].end(),words[j].begin(),words[j].end(),int_sec); //或者使用 string int_sec; //set_intersection(words[i].begin(),words[i].end(),words[j].begin(),words[j].end(),back_inserter(int_sec)); if(int_sec_end-int_sec==0) m.push_back(words[j].size()); } sort(m.begin(),m.end()); if(m.size()>0) Max_len.push_back(words[i].size()*m[m.size()-1]); else Max_len.push_back(0); } sort(Max_len.begin(),Max_len.end()); return Max_len[Max_len.size()-1]; } };再附上某大神的位操作解法
int maxProduct(vector<string>& words) { vector<int> mask(words.size()); int result = 0; for (int i=0; i<words.size(); ++i) { for (char c : words[i]) mask[i] |= 1 << (c - 'a'); for (int j=0; j<i; ++j) if (!(mask[i] & mask[j])) result = max(result, int(words[i].size() * words[j].size())); } return result; }其中
mask[i] |= 1 << (c - 'a');由于之前接触位操作较少,所以把这句变得更通俗一点
mask[i] =mask[i]| 1 << (c - 'a');这句话的意思是这样的: 原来初始化的mask值为
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0当进来一个a时 a-a=0,所以在1的右侧添加 0 个 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1按位或后为:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1当进来一个b时 b-a=1,所以在1的右侧添加 1 个 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0与上面的结果取按位或为
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1所以只有当两个字符都有 a b 的时候 他们在取按位与的时候该位才会为1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1所以当字符有重复数字的时候,二者的按位与必然有1,所以他们的十进制数一定大于0
if (!(mask[i] & mask[j]))if 里面的数则必然非0,取!后必然为0 反之 if 中的数必然为0 取!后为1,执行计算字符串二者长度的乘积操作
result = max(result, int(words[i].size() * words[j].size()));mask是vector int 型的,所以mask[i]是 int 型的,而英文字符是26位的,32位机器下的 int 型为4个字节 32 位正好可以存放,而leetcode的编译器确实也是32位 可以 sizeof(int)
由于博主的学识有限,难免会出现错误,欢迎大家在评论区批评,指正,交流,也欢迎大家对博文的内容上的继续补充