题目

给定一组 唯一 的单词，找出所有不同 的索引对 (i, j)，使得列表中的两个单词，words[i] + words[j] ，可拼接成回文串。

示例 1:

输入: ["abcd","dcba","lls","s","sssll"]
输出: [[0,1],[1,0],[3,2],[2,4]] 
解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

示例 2:

输入: ["bat","tab","cat"]
输出: [[0,1],[1,0]] 
解释: 可拼接成的回文串为 ["battab","tabbat"]

方案一（暴力求解）

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        if not words:
            return []

        ret = []
        for i in range(len(words)):
            for j in range(len(words)):
                if i != j and self.isPairs(words[i] + words[j]):
                    ret.append([i, j])
        return ret


    def isPairs(self, word) -> bool:
        '''判断一个词是否是回文词'''
        length = len(word)
        for i in range(length // 2):
            if word[i] != word[length - i - 1]:
                return False

        return True

• leetcode 超时

方案二（hash表）

• 参答案解析理论后实现

class Solution:
    def palindromePairs(self, words: [str]) -> [[int]]:
        d = {word: i for i, word in enumerate(words)}

        ret = []
        for i, word in enumerate(words):
            # 本身是回文串
            if self.isPairs(word) and "" in d and d[""] != i:
                ret.append([d[""], i])
                ret.append([i, d[""]])

            for j in range(1, len(word) + 1):
                # 前N个字符是回文串切后续字符的翻转在单词列表中，并且不是同一个词
                if self.isPairs(word[:j]) and word[j:][::-1] and word[j:][::-1] in d and d[word[j:][::-1]] != i:
                    ret.append([d[word[j:][::-1]], i])
                if self.isPairs(word[j:]) and word[:j][::-1] and word[:j][::-1] in d and d[word[:j][::-1]] != i:
                    ret.append([i, d[word[:j][::-1]]])

        return ret

    def isPairs(self, word) -> bool:
        '''判断一个词是否是回文词'''
        length = len(word)
        for i in range(length // 2):
            if word[i] != word[length - i - 1]:
                return False

        return True

leetcode 大佬的实现，性能高很多

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        #本身就是回文串单词
        palidStr = []
        #翻转单词记录位置
        rev_words = {}
        res = []
        for idx, word in enumerate(words):
            rev_words[word[::-1]] = idx
            #为了防止数组里有空字符串（""）
            if word == word[::-1]:
                palidStr.append(idx)

        for idx, word in enumerate(words):
            if word:
                # 这里没有 len(word) + 1
                for i in range(len(word)):
                    left, right = word[:i], word[i:]    #包含了左边为空的情况
                    #是否存在在单词左边加 使得成为回文串
                    if left == left[::-1] and right in rev_words and idx != rev_words[right]:
                        res.append([rev_words[right],idx])
                    #是否存在在单词右边加 使得成为回文串
                    if right == right[::-1] and left in rev_words and idx != rev_words[left]:
                        res.append([idx, rev_words[left]]) #包含了回文串加空字符串的情况
            else:
                for loc in palidStr:
                    if loc != idx:
                        res.append([idx, loc]) #只需增加一次，非空的时候左边为空字符串已经考虑过了
        return res

原文

https://leetcode-cn.com/explore/learn/card/trie/168/practical-application-ii/654/
https://leetcode-cn.com/problems/palindrome-pairs/solution/hui-wen-dui-by-leetcode/