O(n * m^2) simple Python solution with explanation


  • 0
    M
        def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]
        """
        # return prefix, suffix of a word, 'abc' -> ['','abc'], ['a','bc']..['abc','']
        def partition_word(word): # O(m) time where m is length of word, O(1) space with generator
            for i in xrange(len(word)+1):
                yield word[:i], word[i:]
        
        def isPalindrome(word): # O(m/2) time, O(1) space
            if not word: return False
            pos = (len(word)-len(word)%2)/2    
            for i in xrange(pos):
                if word[i] != word[-1-i]:
                    return False
            return True
        
        match = []
        # Create table with word as key and index as value, O(n) space
        words_table = dict((word, i) for i, word in enumerate(words))
        
        for word, i in words_table.items(): # O(n * m^2)
            # Handle single case for non-palindromic word
            # 'abc' + {'cba'}
            if len(word) > 1 and not isPalindrome(word) and word[::-1] in words_table:
                match.append([i, words_table[word[::-1]]])
                
            for prefix, suffix in partition_word(word): # O(m * m)
                # {'cba'} + palindrome + 'abc'
                # {''} + palindrome + ''
                if isPalindrome(prefix) and suffix[::-1] in words_table: 
                    match.append([words_table[suffix[::-1]], i])
                # 'abc' + palindrome + {'cba'}
                # '' + palindrome + {''}
                if isPalindrome(suffix) and prefix[::-1] in words_table:
                    match.append([i, words_table[prefix[::-1]]])
                
                    
        return match

Log in to reply
 

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