一、题目

Maximum Product of Word Lengths

二、解题

输入：一个字符串列表
输出：计算每两个没有交集的字符串，算出乘积最大的。
常规解法，两重遍历，判断两个数是否没有交集，使用转外为list和set对比长度，一样则返回True。

三、尝试与结果

class Solution(object):
    def isDiff(self,a,b):
        s = a+b
        if len(list(s)) == len(set(list(s))):
            return True
        else:
            return False

    def maxProduct(self, words):
        maxLen = 0 
        for i in range(len(words)):
            for j in range(i,len(words)):
                if self.isDiff(words[i],words[j]):
                    lens = len(words[i]) * len(words[j])
                    maxLen = lens if lens>maxLen else maxLen
        return maxLen

结果:TL

再次尝试，使用二进制。

class Solution(object):
    def fomatWord(self,words):
        fwords = []
        for word in words:
            fword = 0
            for letter in word:
                fword |= 1 << ord(letter) - ord('a')
            fwords.append(fword)
        return fwords

    def isDiff(self,a,b):
        if a & b == 0:
            return True
        else:
            return False

    def maxProduct(self, words):
        fwords = self.fomatWord(words)
        maxLen = 0 
        for i in range(len(words)):
            for j in range(i + 1,len(words)):
                if self.isDiff(fwords[i],fwords[j]):
                    lens = len(words[i]) * len(words[j])
                    maxLen = lens if lens>maxLen else maxLen
        return maxLen

结果：AC

说明：
1）把每一个单词，都转化为二进制数，规则是把26个英文字母映射到二进制数的每一位，例如a映射到第0位、b第一位。如果一个数是abc，那么这个数是00，0000，0000，0000，0000，0000，0111。
2）进行这个操作是通过二进制移位，然后或上本身，fword |= 1 << ord(letter) - ord('a')，当letter是b时，ord（letter）-ord（'a'）等于1，把1往左移1位（其实就是把第二位变成了1、即存在b，第二位变为1）。
3）两个数不同是通过a & b = 0来实现的，因为没有相同字母，意味着两个数在任意一位上，都不同（0和1），而0&1 = 0