Python O(n*avg_len^2) Solution


  • 1
    C
    class Solution(object):
        def isPalindrome(self, s):
            for i in xrange(len(s)/2):
                if (s[i] != s[len(s)-1-i]): return False
            return True
    
        def palindromePairs(self, words):
            res = []
            if not words: return res
    
            # Hash the indices
            n = len(words)
            idx = {words[i] : i for i in xrange(n)}
    
            for word in words:
                for i in xrange(len(word)):
                    prefix, rprefix = word[:i], word[:i][::-1]
                    suffix, rsuffix = word[i:], word[i:][::-1]
                    if self.isPalindrome(prefix) and (rsuffix in idx) and idx[rsuffix] != idx[word]:
                        res.append([idx[rsuffix], idx[word]])
                    if self.isPalindrome(suffix) and (rprefix in idx) and idx[rprefix] != idx[word]:
                        res.append([idx[word], idx[rprefix]])
                        if not rprefix : res.append([idx[rprefix], idx[word]]) # deal with empty string
            return res

  • 1
    C

    nice solution. Your complexity analysis is based on assumption that "rsuffix in idx" is always O(1) which is not very solid, although mostly true. Changing your isPalindrome(s) check to : return s == s[::-1] will save 1/3 - 1/4 time.


Log in to reply
 

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