LeetCode Maximum Product of Word Lengths

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。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *