Python Solution Using Set Intersection


  • 4

    The worst time complexity of this solution is still max( O(n * n), O(n * m) ) :|

    We introduce array es and dict ml, where

    es[x] stores words(represented by an integer) which doesn't contain letter x

    ml[x] stores the max length of words whose integer value == x

    Python Code:

    class Solution(object):
        def maxProduct(self, words):
            """
            :type words: List[str]
            :rtype: int
            """
            es = [set() for x in range(26)]
            ml = collections.defaultdict(int)
            for w in words:
                num = sum(1 << (ord(x) - ord('a')) for x in set(w))
                ml[num] = max(ml[num], len(w))
                for x in set(string.lowercase) - set(w):
                    es[ord(x) - ord('a')].add(num)
            ans = 0
            for w in words:
                r = [es[ord(x) - ord('a')] for x in w]
                if not r: continue
                r = set.intersection(*r)
                for x in r:
                    ans = max(ans, len(w) * ml[x])
            return ans
    

    Ref: http://bookshadow.com/weblog/2015/12/16/leetcode-maximum-product-word-lengths/


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.