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表示没有共同字符。

完整代码如下:

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;
	}
};

本代码提交AC,用时69MS。

Leave a Reply

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