Python solution, TLE, can anyone tell me why? thx


  • 0
    J
    class Solution(object):
        def maxProduct(self, words):
            """
            :type words: List[str]
            :rtype: int
            """
            dic={}
    
            for word in words:
                a = 0
                l = set(word)
                mask = 1
                for i in l:
                    a += mask << ord(i)-ord('a')
                dic[word] = a
            res = 0
            for i in xrange(len(words)-1):
                for j in xrange(i+1,len(words)):
                    if dic[words[i]] + dic[words[j]] == dic[words[i]]^dic[words[j]]:
                        res = max(res,len(words[i])*len(words[j]))
    
            return res

  • 0
    S
    res = max(res,len(words[i])*len(words[j]))
    

    You calculate the length of each word every time in the loop. Just pre-calculate the length for each word and save it in a list and do lookups in the loop.

    The length of each word could be big.


Log in to reply
 

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