leetcode_318

发表于   |   分类于

Maximum Product of Word Lengths

题目戳这

题意

给定一个字符串数组，找出一对字符串，下标为i,j，求length(word[i])*length(word[j])最大，当word[i]和word[j]没有公共的字符情况下。

解法

还是通过位运算来进行计算，，位运算真的很神啊。。。
我们用 1<<(x-‘a’)来将每个字母转换为二进制表示，然后把整个字符串的每个这种二进制进行或运算，得到的结果就是将该字符串中所有字母对应的二进制位都置为1，这样整个结果就能代表该字符串了。当然，也有可能两个字符串的二进制表示是一样的，比如’ab’和’abab’，那么我们可以只记录后面那个字符串对应的值，因为它长度较长，得到的结果肯定更优。 这个二进制和长度之间的关系可以用字典来记录。

最后如果两个字符串的二进制与的结果为0，说明它们之间的字符没有交集，计算它们的len1*len2即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        mp = {}
        for word in words:
            mask = 0
            for cr in word:
                mask |= 1<<(ord(cr)-ord('a')) # 将所有字母对应的位进行与运算
                # 如果有两个字符串的位运算相等，比如'aba','abab'，那么就取长度长的
            mp[mask] = max(mp.get(mask, 0), len(word)) 
        
        ans = 0
        for x in mp:
            for y in mp:
                if not x&y:     # x&y==0,说明x与y没有任何字母的交集，x,y无公共字符
                    ans = max(ans, mp[x]*mp[y])
        
        return ans