[LeetCode] 318. Maximum Product of Word Lengths

- Problem

318. Maximum Product of Word Lengths

- 내 풀이 (Brute-force)

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        N = len(words)
        answer = 0
        for i in range(N-1):
            set_words = set(words[i])
            for j in range(i+1, N):
                if not (set_words & set(words[j])):
                    answer = max(answer, len(words[i]) * len(words[j]))

        return answer

- 결과

뭐지 이 끔찍한 결과는

- 내 풀이 2 (Bit Manipulation)

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        dic = defaultdict(lambda: 0)
        answer = 0

        for word in words:
            mask = 0
            for c in set(word):
                mask |= 1 << (ord(c) - 97)
            dic[mask] = max(dic[mask], len(word))
       
        for i in dic.keys():
            for j in dic.keys():
                if not (i & j):
                    answer = max(dic[i] * dic[j], answer)

        return answer

- 결과

편안...