LeetCode刷题实战318：最大单词长度乘积-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 最大单词长度乘积，我们先来看题面：

https://leetcode-cn.com/problems/maximum-product-of-word-lengths/

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

给定一个字符串数组 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 
解释: 不存在这样的两个单词。

解题

https://blog.csdn.net/qq_41855420/article/details/88370883

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

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