LeetCode Maximum Product of Word Lengths
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.
Example 1:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".
Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".
Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.
给定一个字符串数组，问两个没有共同字母的字符串的长度之积最大是多少，如果不存在这样两个字符串，则返回0。 常规思路是两层循环，判断两个字符串是否有共同字符，没有就把它俩的长度乘起来，更新最大值。 问题的关键就是如果快速的判断两个字符串是否有共同字符，常规思路是把一个字符串Hash，然后对另一个字符串的每个字符，看是否在前一个字符串中出现。快速方法是，因为题目说明字符串中只有小写字母，也就是只有26种情况，所以我们可以对这26个字母编码成一个26长的bit位，用一个int存储足够。这样判断两个字符串是否有共同字符，只需要把两个int相与，等于0表示没有共同字符。 完整代码如下： [cpp] class Solution { public: int maxProduct(vector<string>& words) { int ans = 0; vector<int> mask(words.size(), 0); for (int i = 0; i < words.size(); ++i) { for (int j = 0; j < words[i].size(); ++j) { mask[i] |= 1 << (words[i][j] – ‘a’); } for (int k = 0; k < i; ++k) { if ((mask[i] & mask[k]) == 0) // 注意 == 的优先级高于 & ans = max(ans, int(words[i].size()*words[k].size())); } } return ans; } }; [/cpp] 本代码提交AC，用时69MS。]]>