LC318：最长单词长度乘积

这题标准解法位运算，但是确实没想到可以这样做，记录一下。

Problem: 318. 最大单词长度乘积

思路

1. 暴力做法 167/168 ,太🐕了，卡样例

2. 位运算，从未设想的道路

位运算思路

位运算做法，用一个int的数（2^31-1)也就是31位，完全可以存储26个字母对应的位数。

举例：一个字符串 abcd,如果用一个 int 的数 x，初始值为0，那它的二进制数就是 000~~~,然后通过位（或）运算把每个出现的字符都放在 x 的二进制数对应位置上，得到 1111000~~，如果再来一个字符串 efgj就得到了对应的数 y 的二进制数 0000111001000 ~~~，这两个二进制数作与运算，如果为0就说明没有重复字符，可以求积。

位运算

class Solution {
public:
//没想到过用位运算
    int maxProduct(vector<string>& words) {
            int len = words.size();
            vector<int> st(len);   //每个字符串都对应一个“掩码”
            for(int i = 0; i < len; i++){
                string word = words[i];
                int size = word.size();
                for(int j = 0; j < size; j++){
                    st[i] |= 1 << (word[j] - 'a');  //出现的字符，映射到对应的位上
                }
            }
            int ans = 0;
            for(int i = 0; i < len; i++){
                for(int j = i + 1; j < len; j++){
                    if((st[i] & st[j]) == 0){   //不存在相同字符
                        ans = max(ans, (int)(words[i].size() * words[j].size()));
                    }
                }
            }
            return ans;
    }
};

暴力

[]
class Solution {
public:
    //暴力一发
    //没两个字符串，先判断是否有重复字符，有的话就跳过，没有就求积
    bool check(string &a, string &b){
        int st[26] = {0};   //每个字符出现的个数
        for(int i = 0; i < a.size(); i++){
            st[a[i] - 'a']++;
        }
        for(int i = 0; i < b.size(); i++){
            if(st[b[i]-'a'] > 0) return false;  //只要已经存在了这个字符，就说明b与a重复了
        }
        return true;
    }

    int maxProduct(vector<string>& words) {
        //取子串
        int len = words.size();
        int ans = 0;
        for(int i = 0; i < len; i++){
            for(int j = i + 1; j < len; j++){
                string a = words[i]; string b = words[j];
                if(check(a, b)){
                    ans = max(ans, (int)(a.size() * b.size()));
                    //长见识了，字符串长度返回的是 unsigned long int 类型，和int不匹配
                }
            }
        }
        return ans;
    }
};