题目描述：

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.

题目大意：

给定一个字符串数组words，寻找length(words[i]) * length(words[j])的最大值，其中两个单词不包含相同字母。你可以假设每一个单词只包含小写字母。如果不存在这样的两个单词，返回0。

测试用例见题目描述。

解题思路：

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和字典ml。

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

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

首次遍历words，计算words[i]对应的数字num，并找出words[i]中所有未出现的字母，将num加入这些字母在es数组中对应的位置。

二次遍历words，计算words[i]中未出现过字母所对应的数字集合的交集，从字典ml中取长度的最大值进行计算。

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):
                es[ord(x) - ord('a')].add(num)
        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

 

本文链接：http://bookshadow.com/weblog/2015/12/16/leetcode-maximum-product-word-lengths/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码