题目描述

给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

解题思路

在二进制中数字的每个数位要么是0要么是1，因此可以用26个二进制的数位来表示一个字符串的不重复的字符（模拟哈希），一个int型整数的二进制形式有32位，但只需要26位就可以表示一个字符串中出现的字符，所以是可行的。在最后判断两个字符串是否包含相同字符时，遵循如下规则：

• 如果两个字符串中包含相同的字符，那么它们对应的整数相同的某个数位都为1，两个整数的与运算将不会等于0；
• 如果两个字符串中没有相同的字符，那么它们对应的整数的与运算的结果等于0。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        if (words.empty()) return 0;

        vector<int> flags(words.size(), 0);
        for (int i = 0; i < words.size(); ++ i)
        {
            for (char &ch : words[i])
            {
                //flags[i]用来记录字符串words[i]中出现的字符
                flags[i] |= 1 << (ch - 'a');
            }
        }

        int res = 0;
        for (int i = 0; i < words.size(); ++ i)
        {
            for (int j = i + 1; j < words.size(); ++ j)
            {
                //如果两个字符串没有相同的字符
                if ((flags[i] & flags[j]) == 0)
                {
                    int tmp = words[i].length() * words[j].length();
                    res = max(res, tmp);
                }
            }
        }

        return res;
    }
};