一敬尺、題目
Maximum Product of Word Lengths
二枚尼、解題
輸入：一個(gè)字符串列表
輸出：計(jì)算每?jī)蓚€(gè)沒有交集的字符串贴浙，算出乘積最大的。
常規(guī)解法署恍，兩重遍歷崎溃，判斷兩個(gè)數(shù)是否沒有交集，使用轉(zhuǎn)外為list和set對(duì)比長(zhǎng)度盯质，一樣則返回True袁串。
三、嘗試與結(jié)果
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
結(jié)果:TL
再次嘗試呼巷，使用二進(jìn)制囱修。
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
結(jié)果：AC
說明：
1）把每一個(gè)單詞，都轉(zhuǎn)化為二進(jìn)制數(shù)朵逝，規(guī)則是把26個(gè)英文字母映射到二進(jìn)制數(shù)的每一位蔚袍，例如a映射到第0位、b第一位配名。如果一個(gè)數(shù)是abc啤咽，那么這個(gè)數(shù)是00，0000渠脉，0000宇整，0000，0000芋膘，0000鳞青，0111。
2）進(jìn)行這個(gè)操作是通過二進(jìn)制移位为朋，然后或上本身臂拓，fword |= 1 << ord(letter) - ord('a')，當(dāng)letter是b時(shí)习寸，ord（letter）-ord（'a'）等于1胶惰，把1往左移1位（其實(shí)就是把第二位變成了1、即存在b霞溪，第二位變?yōu)?）孵滞。
3）兩個(gè)數(shù)不同是通過a & b = 0來實(shí)現(xiàn)的，因?yàn)闆]有相同字母鸯匹，意味著兩個(gè)數(shù)在任意一位上坊饶，都不同（0和1），而0&1 = 0
