11-line Python solution, easy to understand, mix all words + all reversed words then use common prefix

  • 5

    Sort all words and all reversed words. One word (call it A) is the prefix of the following words (call it B). If A is B's prefix and one is reversed one is not, and their indexes are different, then we find a palindrome pair.

    def palindromePairs(self, words):
        # 0 means the word is not reversed, 1 means the word is reversed
        words, length, result = sorted([(w, 0, i, len(w)) for i, w in enumerate(words)] +
                                       [(w[::-1], 1, i, len(w)) for i, w in enumerate(words)]), len(words) * 2, []
        for i, (word1, rev1, ind1, len1) in enumerate(words):
            for j in xrange(i + 1, length):
                word2, rev2, ind2, _ = words[j]
                if word2.startswith(word1):
                    if ind1 != ind2 and rev1 ^ rev2:
                        rest = word2[len1:]
                        if rest == rest[::-1]: result += ([ind1, ind2],) if rev2 else ([ind2, ind1],)
        return result

  • 0

    This is an elegant solution. But the number of lines is not 11, should be around 15 because:
    In line one, there is no semantic reason of combining words, length, and result in one line.
    Similarly for the very long if if else...

  • 0

    Right, I just want to make the code shorter. For result += ([ind1, ind2],) if rev2 else ([ind2, ind1],), I think it's more readable (like English) compared with if rev2: result += ([ind1, ind2],) else: result += ([ind2, ind1],) .

  • 0

    however the complexity is O(n^2)

  • 0

    Unfortunately yes

Log in to reply

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