frendguo's blog

【LeetCode】318. Maximum Product of Word Lengths

原文地址:https://leetcode.com/problems/maximum-product-of-word-lengths/#/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.

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.

刚开始看到这个的时候,首先想到的就是怎么高效的判断两个字符串是否有相同的字符。显然直接遍历每个字符串中的每个字符这样不太实际。

然后看到了一位大神的神操作,就是将字符串中的26个字符和整数的低26位做了个一对一的映射,然后就能很方便的判断两个字符串有木有相同字符了。

然后,代码就简单了:

static int CalcMaxProduct(string[] words)
{
	if (words == null || words.Length == 0) 
	{
		return 0;
	}

	int n = words.Length;
	int maxVal = 0;
	int[] mask = new int[n];
	for (int i = 0; i < n; i++)
	{
		mask[i] = 0;
		foreach (var ch in words[i])
		{
			mask[i] |= 1 << (ch - 'a');
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			int tmp = words[i].Length * words[j].Length;
			if ((mask[i] & mask[j]) == 0 
				&& words[i].Length * words[j].Length > maxVal)
			{
				maxVal = words[i].Length * words[j].Length;
			}
		}
	}

	return maxVal;
}

完美解决~

Happy Coding!o(* ̄▽ ̄*)o

Add comment

Loading