位运算

---

题目详情

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

---

示例1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。
1
2
3

示例2:

输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4 
解释：这两个单词为 "ab", "cd"。
1
2
3

示例3:

输入：words = ["a","aa","aaa","aaaa"]
输出：0 
解释：不存在这样的两个单词。
1
2
3

思路:
本题的关键显然是判断两个单词是否有相同字母,如果遍历两两比较,显然复杂度较高
我们可以利用位运算,因为题目要求两个无相同字母的最长的长度乘积,所以我们可以建立一个hash
利用位左移运算得到每个字母独特的1的位置(int类型长度为32,字母一共26个,所以位置足够用)
再利用或运算|=将其赋予mask,最后每个单词都会有自己的一个独特的mask
也有可能存在一模一样mask的单词(存在重复字母比如meet和met的mask就相同)
我们只需要每次更新mask对应的length为较长的即可
在我们遍历一个个单词的时候,遍历完一个我们就用这个mask和hash里已存的mask按位与
当按位与为0时就更新ans为较长的乘积,最后我们遍历完单词,也求出了最终答案

我的代码：

class Solution 
{
public:
    int maxProduct(vector<string>& words) 
    {
        unordered_map<int, int> hash; //建立hash存储字符串
        int ans = 0;
        for (const string & word : words) //对于每个单词
        {
            int mask = 0, size = word.size(); 
            for (const char & c : word) //每个单词的每个字母
            {
                //c-'a'就是c到a的距离,然后将1左移这么多距离
                //就能将000..01这个1移到专属于c的一个位置
                //然后利用mask与它做或运算,从而将这个位置的1
                //赋给mask,最后遍历完单词每个字母,就会得到一个独特的总数
                mask |= 1 << (c - 'a');
            }
            //如果有同mask(有重复字母)的词我们取较长的
            //例如meet和met具有相同的mask,我们取length就是4
            hash[mask] = max(hash[mask], size);
            //遍历hash寻找满足的h_mask
            for (const auto& [h_mask, h_len]: hash)
            {
                if (!(mask & h_mask)) //按位与如果不存在相同字母
                {
                    ans = max(ans, size * h_len);//就更新ans为较大值
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

位运算常用技巧