Can anyone tell me why does my python N*k^2 solution exceed time limit?


  • 0
    H

    Can anyone tell me why does my python N*k^2 solution exceed time limit?

    class Solution(object):
        def palindromePairs(self, words):
            """
            :type words: List[str]
            :rtype: List[List[int]]
            """
            map_ = {word:i for i, word in enumerate(words)}
            #print map_
            res = []
            for index,w in enumerate(words):
                for i in xrange(0, len(w)*2, 1):
                    left = i//2-1
                    right = left+2 if i&1 else left+1
                    missing = []
                    if i <= len(w):
                        while right < len(w):
                            if left >= 0:
                                if w[left] != w[right]: 
                                    missing = ['-1']
                                    break
                                left -= 1
                            else:
                                missing.append(w[right])
                            right += 1
                        
                        missing = "".join(missing[::-1])
                        if missing == "" and missing != w and missing in map_:
                            res.append((map_[missing], index))
                            res.append((index, map_[missing]))
                        elif missing != w and missing in map_:
                            res.append((map_[missing], index))
                    else:
                        while left >= 0:
                            if right < len(w):
                                if w[left] != w[right]:
                                    missing = ['-1']
                                    break
                                right += 1
                            else:
                                missing.append(w[left])
                            left -= 1
                        missing = "".join(missing)
                        #print missing, i, w
                        if missing != w and missing in map_:
                            res.append((index, map_[missing]))
    
            return res
    

Log in to reply
 

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