一、题目
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
