[算法题解]leetcode 318. 最大单词长度乘积

题目
首先读题，题目要求两个字符串不能含有公共字母，这句话还隐含了一个意思就是我们在比较两个字符串时，可以先看两个字符串出现的字母有没有相同的，那么我们可以将字符串处理成每个字母只出现一次，再进行比较，但是进一步想，一共只有26个字母，一个int类型的数据可以储存32位的01，我们是不是可以只用一个int数据就可以表示一个字符串所包含的字符呢？
我们用1表示该位置的字母出现，例如：“a”，我们可以表示为000...01，“ab”就是000...0011，明白了吗？
所以我们可以这样处理当前字符

n |= (1 << v - 'a')

n就是该字符串处理后对应的数字，v就是s中的一个字符。
处理好s之后我们还要记录下n对应的最大长度，直接用max函数即可。
这里我用哈希表来实现：

unordered_map<int,int> hash;
for(string &s : words) {
    int n = 0;
    for(char v : s){
        n |= (1 << (v - 'a'));
    }
    hash[n] = max(hash[n],(int)s.size());
}

先迭代words再迭代s储存我们想要的结果，之后我们就需要实现计算最大长度积了。
怎么判断两个n是否在相同的位都有1？
做算数与运算即可，只有他们没有公共位含有1时结果才为0.

if(hash.size()<2)   return 0;
int ans{};
for(auto it = hash.begin();it != hash.end();it++) {
    auto at = it;
    at++;
    for(;at != hash.end();at++) {
        if(!(it->first & at->first))
            ans = max(ans,int(it->second*at->second));
    }
}

以上就是所有内容。