9 Lines Python Solution

  • 0

    For any palindrom combination, one of the following things should happen

    1. Palindrome = words[j] + words[i][:k] + words[i][k:]
      words[i][:k] is a palindrom and words[i][k:] is the reverse of words[j] (k starts at 0 ends at len(words[i])
    2. Palindrome = words[i][:k] + words[i][k:] + words[j]
      words[i][k:] is a palindrom and words[i][:k] is the reverse of words[j] (k ends before len(words[i]) to avoid duplication)

    Pretty straightforward.

        def palindromePairs(self, words):
            rev, res = {word[::-1]: i for i, word in enumerate(words)}, []
            for i, w in enumerate(words):
                for k in xrange(len(w) + 1):
                    if w[:k] == w[:k][::-1] and w[k:] in rev and rev[w[k:]] != i:
                        res.append([rev[w[k:]], i])
                    if w[k:] == w[k:][::-1] and w[:k] in rev and rev[w[:k]] != i and k < len(w):
                        res.append([i, rev[w[:k]]])
            return res

Log in to reply

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