leetcode_336_回文对

回文对

描述

困难

给定一组 互不相同 的单词， 找出所有不同的索引对(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]]:
        res = []
        n = len(words)
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if self.is_palindrome(words[i] + words[j]):
                    res.append([i, j])
        return res

    def is_palindrome(self, s):
        right = len(s) - 1
        left = 0
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

如果有两个字符串s1和s2，他们拼接后有三种情况

• len(s1) = len(s2)，那么只需比较s1 与s2[::-1] 是否相同即可
• len(s1) > len(s2)
  • s2 拼接在s1后面，那么s1的前len(s2)个字符等于s2[::-1]，中间len(s2) 到len(s1) 个字符为回文串
    • 比如s1为"abc"，s2为"ba"，判断s1 前2个字符是否为s2 的逆序"ab"，且s1剩余字符"c"是否为回文串
  • s2 拼接在s1前面，那么s1 的后len(s2) 个字符等于s2[::-1]，s1的前len(s1)-len(s2) 个字符为回文串
    • 比如s1为"abc"，s2为"cb"，判断s1 后2个字符是否为s2 的逆序"bc"，且s1剩余字符"a"是否为回文串
• len(s1) < len(s2)，将s1与s2交换即变成上一种情况

算法

将所有字符串保存在字典中，键为该字符串，值为其下标

然后遍历每个字符串，可以看作为s1

并且将字符串分为 [:j] 和 [j:] 两部分

• 如果第一部分的逆序存在于字典中，且第二部分为回文串，则为上面第二种情况的第一种情况
• 如果第二部分的逆序存在于字典中，且第一部分为回文串，则为上面第二种情况的第二种情况

注意

在遍历时忽略上面第三种情况，默认为第一或二种情况

• 可以通过 j 将字符串s1划分为 s1 和 空字符串 "" ，此时为第一种情况
• 分割后的子串和查找字典中是否存在该子串的逆序，则字典中的字符串长度要小于当前正在遍历的字符串，所以可以看做s2

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        res = []
        dic = {word: i for i, word in enumerate(words)}
        for i, word in enumerate(words):
            for j in range(len(word) + 1):
                temp1 = word[:j] 
                temp2 = word[j:]
                if temp1[::-1] in dic and dic[temp1[::-1]] != i and temp2 == temp2[::-1]:
                    res.append([i, dic[temp1[::-1]]])

                if j > 0 and temp2[::-1] in dic and dic[temp2[::-1]] != i and temp1 == temp1[::-1]:
                    res.append([dic[temp2[::-1]], i])
        return res