LeetCode 最大单词长度乘积

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

示例 1:

输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。

示例 2:

输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。

示例 3:

输入: ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。

方法一：蛮力法。穷举两个字符串，然后判断是否存在相同的字符，如果不存在则更新单词长度乘积。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int result = 0;
        int wordsSize = words.size();
        //対第一个字符串穷举
        for (int nowIndex = 0; nowIndex < wordsSize; ++nowIndex){
            //标记第一个字符串各个字符出现
            map<char, bool> firstMap;
            for (auto ch : words[nowIndex]){
                firstMap[ch] = true;
            }
            //穷举第二个字符串
            for (int afterIndex = nowIndex + 1; afterIndex < wordsSize; ++afterIndex){
                int afterWordSize = words[afterIndex].size(), tempIndex = 0;
                //判读第一个、第二个字符串是否存在相同的字符
                for (; tempIndex < afterWordSize; ++tempIndex){
                    if (firstMap[words[afterIndex][tempIndex]]){
                        break;
                    }
                }
                //如果不存在相同的字符
                if (afterWordSize == tempIndex){
                    result = max(int(afterWordSize * words[nowIndex].size()), result);//更新结果
                }
            }
        }
        return result;
    }
};

方法二：使用位操作。
小写字母一共有26，而int型有32位，所以每一个小写字母占据一个位。在判断字符是否存在相同的字符时只需要判断是否存在某一位同时为1.

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int result = 0;
        int wordsSize = words.size();
        vector<int> wordToInt(wordsSize, 0);//wordToInt[i]表示words[i]按照字母分别占据以为得到的int数据
        //対第一个字符串穷举
        for (int nowIndex = 0; nowIndex < wordsSize; ++nowIndex){
            //将第一个字符串按照字符占据位，计算为int
            for (auto ch : words[nowIndex]){
                wordToInt[nowIndex] |= (1 << (ch - 'a'));
            }
            //穷举第二个字符串
            for (int afterIndex = 0; afterIndex < nowIndex; ++afterIndex){
                //如果不存在相同的字符
                if ((wordToInt[nowIndex] & wordToInt[afterIndex]) == 0){
                    result = max(result, int(words[nowIndex].size() * words[afterIndex].size()));
                }
            }
        }
        return result;
    }
};