Description:
Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Link:
https://leetcode.com/problems/maximum-product-of-word-lengths/description/
解题方法：
假设我们有n个单词，总共有N个字符。
因为没有找到一种方法可以使有相同字母的单词共享一个key的方法，所以这道题是O(n^2)级别的算法。
因为int有32位，如果把26个字母转化为int上每一个位的0或1。我们可以用根据出现字母的组合来定义一个key并且用int储存这个组合。
Tips:
string::size()返回的是size_type类型的值，所以在使用Max函数的时候要注意转换为int。
Time Complexity：
O(max(N, n^2))
完整代码：
int maxProduct(vector<string>& words)
{
unordered_map<int, int> hash;
for(string str: words)
{
int mask = 0;
for(char ch: str)
{
mask |= (1 << (ch - 'a'));
}
hash[mask] = max(hash[mask], (int)str.size()); //different words may have same mask, so we need to save the max value
}
int maxPrud = 0;
for(auto a: hash)
{
for(auto b: hash)
{
if(!(a.first & b.first)) //a and b have different masks, which means a and b don't share common letter
maxPrud = max(a.second * b.second, maxPrud);
}
}
return maxPrud;
}
