1 題目

給你一個字符串數組 words ，找出並返回 length(words[i]) * length(words[j]) 的最大值，並且這兩個單詞不含有公共字母。如果不存在這樣的兩個單詞，返回 0 。

示例 1：

輸入：words = [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]
輸出：16
解釋：這兩個單詞為 “abcw”, “xtfn”。

示例 2：

輸入：words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
輸出：4
解釋：這兩個單詞為 “ab”, “cd”。

2 解析

用一個數字來代指某個包含字母的字符串：低 26 方法來代指字母 a-z 是否出現過。具體的使用是將每個字母轉為比特，然後將整個字符串的所有字母比特進行與運算，得到一個唯一的數字來表示當前字符串。

判斷兩個字符串的字母是否有相同的字母，進行與運算，如果等於0，說明無相同的字母。此時再判斷兩個字符串的長度相乘的結果，選出最大的即可。

時間復雜度 O ( n 2 ) O(n^2) O(n2)

3 Python實現

class Solution:
def maxProduct(self, words: List[str]) -> int:
masks = []
for word in words:
t = 0
for w in word:
u = 1 << (ord(w) - ord('a'))
t |= u
masks.append(t)
ans = 0
for i in range(len(words)):
for j in range(i):
if (masks[i] & masks[j]) == 0:
ans = max(ans, len(words[i]) * len(words[j]))
return ans