###### tags: `Leetcode` `medium` `bit` `string` `python`

# 318. Maximum Product of Word Lengths

## [題目連結:] https://leetcode.com/problems/maximum-product-of-word-lengths/

## 題目:
Given a string array ```words```, return the maximum value of ```length(word[i]) * length(word[j])``` where the two words do not share common letters. If no such two words exist, return ```0```.

**Example 1:**

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

**Example 2:**

Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".

**Example 3:**

Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.

## 解題想法:
* 題目要求:找出兩個不包含重複字符的字串長度，求最大乘積
* 法(1):爆破法
* 用set統計每個string出現字符種類
* 雙for迴圈比較出現是否一樣
* 法(2):Bits判斷
* 想法:
* int有32bits，小寫英文字母有26個
* 將每個字母對應到數字上
* 讓每個string能有個對應的數字編號
* 對於string中若有出現多個相同字母，一律只取一次，避免產生相同編號。
* 編號方式: 要用or

#正確
string1 ='abca'
res=0
for char in string1:
    res |=1<<ord(char)-ord('a') 
print(res)
'''
a=0..... 1*(2**0)
b=1..... 1*(2**1)
c=2..... 1*(2**2)
a=0..... 1*(2**0)
要用or('|')才會避免取到兩次a
res= 1+2+4=7
'''

* 錯誤方式: 不能用累加，計算到重覆字母會導致整體字串編號不唯一

#錯誤方式
string1 ='abca'
res=0
for char in string1:
    res +=1<<ord(char)-ord('a') 
print(res) # res1 = 8

string2='bcb'
res2=0
for char in string2:
    res2+=1<<ord(char)-ord('a')
print(res2)  # res2 = 8

## Python:

class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        n=len(words)
        nums=[0]*n
        res=0
        for pos,curString in enumerate(words):
            #編號
            for char in curString:
                #要用| :目的為能去除重複的字符，讓每個單字有唯一的對應數字
                nums[pos] |= 1<<(ord(char)-ord('a'))
        #比較
        for i in range(n):
            for j in range(i+1,n):
                #若沒交集: &會等於0，但進入if條件須為True(1) 所以加上not
                if not (nums[i]&nums[j]):
                    res=max(res,len(words[i])*len(words[j]))
        return res

if __name__=='__main__':
    result=Solution()
    ans=result.maxProduct(words = ["abcw","baz","foo","bar","xtfn","abcdef"])
    print(ans) #16