# 318. Maximum Product of Word Lengths 最大单词长度乘积

@TOC

## # 题目描述

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:

``````Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".
``````

Example 2:

``````Input: ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".
``````

Example 3:

``````Input: ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.
``````

## # 解题方法

### # set

Python代码如下：

``````class Solution:
def maxProduct(self, words):
"""
:type words: List[str]
:rtype: int
"""
word_dict = dict()
for word in words:
word_dict[word] = set(word)
max_len = 0
for i1, w1 in enumerate(words):
for i2 in range(i1+1, len(words)):
w2 = words[i2]
if not (word_dict[w1] & word_dict[w2]):
max_len = max(max_len, len(w1) * len(w2))
return max_len
``````

### # 位运算

python代码如下：

``````class Solution(object):
def maxProduct(self, words):
"""
:type words: List[str]
:rtype: int
"""
res = 0
d = collections.defaultdict(int)
N = len(words)
for i in range(N):
w = words[i]
for c in w:
d[w] |= 1 << (ord(c) - ord('a'))
for j in range(i):
if not d[words[j]] & d[words[i]]:
res = max(res, len(words[j]) * len(words[i]))
return res
``````

## # 日期

2018 年 7 月 5 日 —— 天气变化莫测呀，建议放个伞 2019 年 3 月 23 日 —— 坚持刷题