本文共 2514 字，大约阅读时间需要 8 分钟。

Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:

Input: ["abcd","dcba","lls","s","sssll"]Output: [[0,1],[1,0],[3,2],[2,4]] Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: ["bat","tab","cat"]Output: [[0,1],[1,0]] Explanation: The palindromes are ["battab","tabbat"]

------------------------------------------------------------------------------------------------

能想到把前后缀拿去查Hash表，这题就成功了一半，另外一半是对于空串和本身回文的处理。直接来会有重复，如以下代码，暂时没有太简洁的去重方式list(set(lst))要求lst里面不能包含list，所以只能转成tuple来玩：

class Solution:    def palindromePairs(self, words):        palin_idx = []        pos = {}        for idx, word in enumerate(words):            pos[word[::-1]] = idx        dup = []        for idx, word in enumerate(words):            wl = len(word)            for i in range(0, wl + 1):                left = word[:i]                right = word[i:] if i < wl else ''                if (left == left[::-1] and right in pos and idx != pos[right]):                    dup.append([pos[right], idx])                if (right == right[::-1] and left in pos and idx != pos[left]):                    dup.append([idx, pos[left]])        res = []        dupset = set()        for item in dup:            if (tuple(item) not in dupset):                dupset.add(tuple(item))                res.append(item)        return ress = Solution()print(s.palindromePairs(["abcd","dcba","lls","s","sssll"]))

另外一种玩法是，把空和本身回文的单独拿出来考虑，注意注释那行的问题：

class Solution:    def palindromePairs(self, words):        pos = {}        palin = []        for idx, word in enumerate(words):            pos[word[::-1]] = idx            if (word == word[::-1]):                palin.append(idx)        res = []        for idx, word in enumerate(words):            wl = len(word)            if (wl == 0):                for i in palin:                    if (i != idx):                        res.append([idx, i])            else:                for i in range(wl):                    left,right = word[:i],word[i:] #left可能为空，right不可能为空                    if (left == left[::-1] and right in pos and idx != pos[right]):                        res.append([pos[right], idx])                    if (right == right[::-1] and left in pos and idx != pos[left]):                        res.append([idx, pos[left]])        return res                    s = Solution()print(s.palindromePairs(["a",""]))

转载地址：http://ttfoi.baihongyu.com/