leetcode 318. Maximum Product of Word Lengths（python）

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第11天，點選檢視活動詳情

描述

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

Example 1:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

Example 2:

Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".

Example 3:

Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.

Note:

2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] consists only of lowercase English letters.

解析

根據題意，給定一個字串陣列 words，返回 length(word[i]) * length(word[j]) 的最大值，其中兩個單詞不能有相同的字母。 如果不存在這樣的兩個詞，則返回 0 。

如果按照常規的思路，我們兩兩進行比對，而假如兩個字串的長度為 L1 和 L2 ，要達到兩個字串中沒有相同的字母，那麼我們的時間複雜度為 O(N^2 * (L1 * L2)) ，這肯定是超時的，我們要保證時間複雜度能夠在 O(N^2) 之內，我們肯定要降低兩個字串的比對效能 O(L1 * L2) 為 O(1) ，根據最近“每日一題”都在考位運算我們就能猜到，這道題也是在考察位運算，我們使用位運算結果來表示字串，一共 26 個字母對應 26 個二進位制位，我們只需要將每個單詞表示成二進位制即可，這樣我們在比對兩個字串所代表的二進位制是隻要判斷 mask[i] & mask[j] 等於 0 即可表示兩個字串沒有相同的字元存在，時間複雜度可以降到 O(1) 。

整體的時間複雜度為 O(N^2) ，空間複雜度為 O(N) 。

解答

class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        N = len(words)
        result = 0
        mask = [0] * N
        for i,word in enumerate(words):
            for j in range(len(word)):
                mask[i] |= 1 << (ord(word[j]) - ord('a'))
        for i in range(N):
            for j in range(i + 1, N):
                a = words[i]
                b = words[j]
                if not mask[i] & mask[j]:
                    result = max(result, len(a) * len(b))
        return result

執行結果

Runtime: 499 ms, faster than 67.32% of Python online submissions for Maximum Product of Word Lengths.
Memory Usage: 14.2 MB, less than 69.91% of Python online submissions for Maximum Product of Word Lengths.

原題連結

http://leetcode.com/problems/maximum-product-of-word-lengths/

您的支援是我最大的動力