Python solution


  • 0
    H
    class Solution(object):
        def maxProduct(self, words):
            """
            :type words: List[str]
            :rtype: int
            """
            wd={}
            prod=0
            for w in words:
                enc=0
                for c in w:
                    enc|= 1<<(ord(c)-ord('a'))
                wd[enc]=max(wd.get(enc,0),len(w))
            for i in wd:
                for j in wd:
                    if not i&j:
                        prod=max(prod,wd[i]*wd[j])
            return prod

  • 0

    I think u can optimize it by sorting, like this:

    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        mask_dict = {}
        begin_ord = ord('a')
        for i, w in enumerate(words):
            enc = 0
            for c in w:
                enc |= 1<<ord(c)-begin_ord
            mask_dict[enc] = max(mask_dict.get(enc, 0),len(w))
        max_len = 0
        sorted_mask = sorted(mask_dict.items(),key=lambda x:x[1], reverse=True)
        for i in range(len(sorted_mask)):
            res = sorted_mask[i][1]*sorted_mask[i][1]
            if res<max_len:
                continue
            for j in range(i+1, len(sorted_mask)):
                if sorted_mask[i][0]&sorted_mask[j][0]==0:
                    res = sorted_mask[i][1]*sorted_mask[j][1]
                    if res>max_len:
                        max_len = res
                        break
        return max_len

Log in to reply
 

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