LeetCode 筆記 - 318. Maximum Product of Word Lengths

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 318. Maximum Product of Word Lengths

給定一個矩陣包含 n 個字串，請找出兩個字串的最大乘積且兩個字串之間不能有相同的字母

解題思維

這題會使用到 Bitwise operation 來加速

首先我們先把每一個字串根據字母分佈轉換成一個數字，意即相同的字母會在一樣的地方出現 1
所以當我們在兩兩配對的時候，就可以用 bit_set_0 & bit_set_1 來判斷是否有重疊的 1 出現

如果有，那就表示有相同的字母
如果沒有，那就表示這是符合規則的

最後的最後，取最大的結果回傳即可

完成 🥰

程式碼

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

解題思維

程式碼

也許你也會想看看