題目在此 318. Maximum Product of Word Lengths
給定一個矩陣包含 n 個字串，請找出兩個字串的最大乘積且兩個字串之間不能有相同的字母
解題思維
這題會使用到 Bitwise operation 來加速
首先我們先把每一個字串根據字母分佈轉換成一個數字，意即相同的字母會在一樣的地方出現 1
所以當我們在兩兩配對的時候，就可以用 bit_set_0 & bit_set_1 來判斷是否有重疊的 1 出現
如果有，那就表示有相同的字母
如果沒有，那就表示這是符合規則的
最後的最後，取最大的結果回傳即可
完成 🥰
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution:
def maxProduct(self, words: List[str]) -> int:
size = len(words)
if size <= 1:
return 0
ord_a = ord('a')
size_map = []
ord_map = []
for w in words:
size_map.append(len(w))
ord_count = 0
for c in w:
ord_count |= 1 << (ord(c) - ord_a)
ord_map.append(ord_count)
result = 0
for i in range(size - 1):
bit_set_0 = ord_map[i]
for ii in range(i + 1, size):
bit_set_1 = ord_map[ii]
if (bit_set_0 & bit_set_1) != 0:
continue
result = max(result, size_map[i] * size_map[ii])
return result
|
相關文章