Simple, short Python, beat 65%

  • 0

    This is my first try, I thought it would be TLE, but it passed. Complexity is O(NL^2), I guess it is similar to others' solutions but I didn't read those.

        def check(self, s):
            for i in range(len(s)/2):
                if s[i] != s[len(s) - i - 1]: return False
            return True
        def palindromePairs(self, words):
            e, ret = {}, []
            for i in range(len(words)): e[words[i]] = i
            for i in range(len(words)):
                r, l = words[i][::-1], len(words[i])
                while l >= 0:
                    if r in e and e[r] != i and self.check(words[i][l:]): ret.append([i, e[r]])
                    r, l = r[1:], l - 1
                r, l = words[i][::-1][:-1], len(words[i]) - 1 # last [:-1] is to remove duplicates of, e.g., "abcd" and "dcba"
                while l >= 0:
                    if r in e and e[r] != i and self.check(words[i][:len(words[i]) - l]): ret.append([e[r], i])
                    r, l = r[:-1], l - 1
            return ret

Log in to reply

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