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;}
};

总结：

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

这篇关于318.最大单词长度乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---