## 题目描述：

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.

## 解题思路：

max( O(n^2), O(n*m) )解法，其中：n为单词个数，m为单词平均长度：

```1. O(n)的预处理，将单词数组words转化为整数数组nums，其中：nums[i] = sum(1 << (ord(x) - ord('a')) for x in set(words[i]))

2. O(n^2)的循环，寻找nums中满足nums[x] & nums[y] == 0的整数对，并计算对应的length(words[i]) * length(words[j])的值```

## Python代码：

``````class Solution(object):
def maxProduct(self, words):
"""
:type words: List[str]
:rtype: int
"""
nums = []
size = len(words)
for w in words:
nums += sum(1 << (ord(x) - ord('a')) for x in set(w)),
ans = 0
for x in range(size):
for y in range(size):
if not (nums[x] & nums[y]):
ans = max(len(words[x]) * len(words[y]), ans)
return ans
``````

### 另一种解法：

es[x]记录所有不包含字母x的单词（单词转化成的数字）

ml[x]记录所有单词对应数字的最大长度

## Python代码：

``````class Solution(object):
def maxProduct(self, words):
"""
:type words: List[str]
:rtype: int
"""
es = [set() for x in range(26)]
ml = collections.defaultdict(int)
for w in words:
num = sum(1 << (ord(x) - ord('a')) for x in set(w))
ml[num] = max(ml[num], len(w))
for x in set(string.lowercase) - set(w):
ans = 0
for w in words:
r = [es[ord(x) - ord('a')] for x in w]
if not r: continue
r = set.intersection(*r)
for x in r:
ans = max(ans, len(w) * ml[x])
return ans
``````

Pingbacks已关闭。

1. 向民 发布于 2015年12月20日 15:35 #

第二张方案非常赞

2. crazy 发布于 2016年2月22日 16:00 #

请问第一段代码第10行最后的逗号是什么作用？

3. Zhao Lou 发布于 2016年2月23日 13:07 #

a = []
a += 3,
is equivalent to a.append(3)