Python solution around 80%


  • 1
    P
    class Solution(object):
        def palindromePairs(self, words):
            """
            :type words: List[str]
            :rtype: List[List[int]]
            """
            if not words:
                return []
            # unique words
            dic = {w:i for i, w in enumerate(words)}
            result = []
            for w in dic:
                i = dic[w]
                # find substring to form palindrome pairs
                # since len(substring) <= len(w), there won't be duplicates
                # if len(substring) == len(w), substring is leading s2[::-1]
                for j in range(len(w)):
                    s1, s2 = w[:j], w[j:]
                    if s1 == s1[::-1] and s2[::-1] in dic and dic[s2[::-1]] != i:
                        result.append([dic[s2[::-1]], i])
                    if s2 == s2[::-1] and s1[::-1] in dic and i != dic[s1[::-1]]:
                        result.append([i, dic[s1[::-1]]])
                # '' is only added once as tail, add it again as lead
                if w != '' and w == w[::-1] and '' in dic:
                    result.append([dic[''], i])
            return result
    

    To make sure that there is no duplicates in result, always try to find pairs that has length <= len(word). Take special care to empty string and equal string. Then you should be good.


Log in to reply
 

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