Leetcode 318 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:
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.

题意分析：
在列表中找两个字符串使得这两个字符串的长度乘积最大，这两个字符串必须满足没有相同字符。
算乘积一个n^2即可，关键在于限制条件，我们固然可以用set来记录字符串然后用 &操作符判断，但是就有点小蠢，空间也相对花费较大
因为只有26个英文字母，我们完全可以用26位长的数字来表示，1代表有，0代表没有，&操作也方便
这种用数字表示字母的思想是一种很经典的思路，已经不止见到过一次了，得记住！

思路：
用一个数组记录长度，用一个数组记录位表示，n^2复杂度解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        n = len(words)
        l = [0] * n
        mask = [0] * n
        for i in range(n):
            l[i] = len(words[i])

        res = 0
        for i in range(n):
            for c in words[i]:
                mask[i] |= 1 << (ord(c)-ord('a'))
            for j in range(i):
                if not mask[i] & mask[j]:
                    res = max(res,l[i] * l[j])
        return res

# O(n^2) time, O(n) space
174 / 174 test cases passed.
dfficulty: medium
Runtime: 409 ms