318.最大单词长度乘积

乘积"/>

318.最大单词长度乘积

​题目来源：

        leetcode题目，网址：318. 最大单词长度乘积 - 力扣（LeetCode）

解题思路：

       位运算+暴力遍历。使用 1 个int 型整数的低 26 位记录所给字符串是否包含某个英文字符，使用 res 记录结果。在遍历时，若两个字符串对应整数相与结果为 0，则无相同字符，更新 res；否则有相同字符。

解题代码：

class Solution {
public:int maxProduct(vector<string>& words) {int res=0;vector<int> cnt(words.size());for(int i=0;i<words.size();i++){cnt[i]=count(words[i]);}for(int i=0;i<words.size();i++){for(int j=i+1;j<words.size();j++){if((cnt[i]&cnt[j])==0 && res<words[i].length()*words[j].length()){res=words[i].length()*words[j].length();}}    }return res;}int count(string str){int res=0;for(int i=0;i<str.length();i++){res=res|(1<<(str[i]-'a'));}return res;}
};

总结：

       官方题解给出了两种解法。第一种是位运算，如上。第二种是位运算优化，使用哈希表记录位掩码及该掩码对应的最长长度，然后遍历哈希表求最大值。