給你一個字符串數組 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”.
Use a number to refer to a string of letters：低 26 way to refer to letters a-z 是否出現過.The specific use is to convert each letter into bits,Then all the letter bits of the entire string are ANDed,Get a unique number to represent the current string.
Check whether the letters of two strings have the same letter,進行與運算,如果等於0,Descriptions do not have identical letters.Then judge the result of multiplying the lengths of the two strings,選出最大的即可.
時間復雜度 O ( n 2 ) O(n^2) O(n2)
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
