LeetCode 318. Maximum Product of Word Lengths

10-20 LeetCode 318. 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.

提供一个字符串数组，找出两个不含有相同字符的字符串，并且这两个字符串的长度的乘积最大。每个字符串都只包含小写字母。如果不存在这样的两个字符串，返回0.

Solution 1:

这题我没有做出来。最开始的想法是用两个for循环把每所有可能的字符串组合遍历一遍。对第一个字符串的每个字符保存在字典中，然后遍历第二个字符串，如果第二个字符串中的字符存在于字典中，跳出循环，否则计算长度乘积。但是这种算法无法通过LeetCode里的数据量大的测试实例。

Solution 2:

参考了网上大神的做法后发现虽然这个想法我有想到，但是不知道怎么实现位操作，平时没怎么遇到过。这道题题目中有一句话是字符串都是小写字母，那就是只有26个字母。我想着是构造一个26位的二进制数，依次对应'a','b'....'z'。如果字符串中包含该字母，则在对应的位置填入1，否则填入0。但是就是卡在不知道怎么构造这个二进制数上。

大神们的做法是取一个int型整数来构造，一个int为32位，取其前26位。这样每个字符串都可以对应一个int型数，比较两个字符串是否含有相同的字符的操作就是对这两个数进行与操作，如果结果为0则不含相同字符，则进行长度乘积计算。

代码：

class Solution(object):
    def maxProduct(self, words):
        d = {}
        for w in words:
            mask = 0
            for c in set(w):
                mask |= (1 << (ord(c) - 97))
            d[mask] = max(d.get(mask, 0), len(w))
        return max([d[x] * d[y] for x in d for y in d if not x & y] or [0])

感想

我之前也遇到过一个题目是通过位运算解决的，我也没有做出来。这样的算法看着比较偏门，但是有时候确实能大大提高算法的效率。