Python O(nk^2) solution


  • 1
    Q

    The idea is actually quite simple. We iterate all words in the given list and add all word reversely into a hashmap, while the reverse word is used as the key, and the index is used as the value.

    Then we loop all words in this list (O(N)). For each word, we check all prefix and suffix word(O(k)). A word is broken into [prefix]+[pfremain], if prefix is in the hashmap and the pfremain is a palindrome(O(k)), then this word and the hashmap[prefix] can make a palindrome pair. Similar thing shall be done for suffix string.

    Note: check hashmap[prefix] != word itself to avoid using a string twice.

    The time complexity is O(N*k^2).

    I have to use a hashset to store the results. Any comment to avoid the duplication here?

       def palindromePairs(self, words):
            """
            :type words: List[str]
            :rtype: List[List[int]]
            """
            def ispalin(word):
                return word == word[::-1] if len(word) > 1 else True
            dicmap = {}
            results = set()
            for i in xrange(len(words)):
                dicmap[words[i][::-1]] = i
            for i in xrange(len(words)):
                word = words[i]
                for k in xrange(0,len(word)+1):
                    prefix = word[:k]
                    pfremain = word[k:]
                    if prefix in dicmap and ispalin(pfremain) and dicmap[prefix] != i:
                        results.add((i,dicmap[prefix]))
                for k in xrange(len(word), -1, -1):
                    suffix = word[k:]
                    sfremain = word[:k]
                    if suffix in dicmap and ispalin(sfremain) and dicmap[suffix] != i:
                        results.add((dicmap[suffix],i))
            return [[res[0],res[1]] for res in results]

  • 0
    J

    In order to avoid duplication I added in a special case to handle the situation where a word is "" (the empty string).

    class Solution(object):
    def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]
        """
        palindromes = []
        reversed_words = {word[::-1]: index for index,word in enumerate(words)}
        for i, word in enumerate(words):
            for j in xrange(len(word)):
                if word[:j] in reversed_words and i != reversed_words[word[:j]]:
                    if word[j:] == word[j:][::-1]:
                        palindromes.append([i, reversed_words[word[:j]]])
                        # handle empty string here 
                        if word[:j] == "":
                            palindromes.append([reversed_words[word[:j]], i])
                if word[j:] in reversed_words:
                    if word[:j] == word[:j][::-1] and i != reversed_words[word[j:]]:
                        palindromes.append([reversed_words[word[j:]], i])
        return palindromes

Log in to reply
 

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