336. 回文对

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/palindrome-pairs

题目

给定一组惟一的单词，找出所有不同的索引对 (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"]

解题思路

思路：枚举，哈希表

首先先看题目，题目中阐明给定的列表中单词惟一，判断是否存在不同索引的单词可能组成回文串？

在示例中，咱们发现组成回文串的字符串长度并非肯定相等的。那么假如，当存在这样的两个字符串单词 a、b 时，a + b 是一个回文串，记录此时两个字符串的长度别离为 a_len、b_len。依据示例，咱们来分状况进行剖析：

1. 当 a_len = b_len 时，那么 a 肯定是 b 的翻转；
2. 当 a_len > b_len 时，因为 b 的长度较小，那么这个时候要组成回文串，a 中必定有局部曾经是回文串。那么将 a 划分为前后 a1 和 a2 两局部，后面 a1 局部是 b 的翻转，而 a2 本身是回文串；
3. 当 a_len < b_len 时，这个状况其实是下面一种的背面。同样将 b 划分为前后 b1 和 b2 两个局部，b1 本身是回文串，而 b2 是 a 的翻转。

从下面的剖析，咱们能够发现，拆解的都是长度较长的字符串。那么，咱们当初能够尝试枚举每个字符串 i，将其认为是较长的字符串，那么咱们当初将其拆分 i1 和 i2。那么这里将会有两种状况：

• 当 i1 是回文串时，那么这里就合乎下面第三种状况，只有找到后续的字符串中序列中是否存在 i2 翻转。
• 当 i2 是回文串时，合乎下面第二种状况，只有找到后续的字符串序列中是否存在 i1 翻转。

在这里，须要留神一种状况，也就是空字符串。因为空字符串也是回文串。那么下面的拆解过程中，当将字符串 i 拆解后，其中 i1 和 i2 某一个为空串时，这种状况其实就合乎后面所剖析的第一种状况。

那么当初须要次要的就是，如何判断拆分后的子串的翻转子串在给定的字符串列表中是否存在？

这里能够思考应用哈希表来存储所有字符串的翻转字符串。那么在查问的拆分后的子串时，只有判断其是否在哈希表中，就能失去后果。

具体的代码实现如下。

代码实现

from typing import List

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        
        def is_palindrome(str, start, end):
            """查看子串是否是回文串"""
            part_word = str[start:end+1]
            return part_word == part_word[::-1]

        def find_reversed_word(str, start, end):
            """ 查找子串是否在哈希表中
            Return:
                不在哈希表中，返回 -1
                否则返回对应的索引
            """
            part_word = str[start:end+1]
            ret = hash_map.get(part_word, -1)
            return ret
        
        # 构建哈希表，存储给定列表中的字符串的翻转字符串
        # 键为翻转字符串，值为未翻转前字符串对应的索引
        hash_map = {}
        for i in range(len(words)):
            word = words[i][::-1]
            hash_map[word] = i
        
        res = []
        
        # 遍历字符串，拆分字符串，进行判断
        for i in range(len(words)):
            word = words[i]
            word_len = len(word)
            # 先判断空串存在的状况，如果以后字符串是回文串（不为空串），将其与以后字符串组合，放入后果中
            if is_palindrome(word, 0, word_len-1) and ""in hash_map and word !="":
                res.append([hash_map.get(""), i])
            for j in range(word_len):
                # 先看划分后左边局部是否是回文串
                if is_palindrome(word, j, word_len - 1):
                    # 查找右边局部子串的翻转是否在哈希表中
                    left_part_index = find_reversed_word(word, 0, j-1)
                    # 当返回的索引值不为 -1，以及不是以后字符串对应的索引时，# 示意存在两个字符串可能组成回文串，将索引增加到后果列表中
                    if left_part_index != -1 and left_part_index != i:
                        res.append([i, left_part_index])
                # 原理同上，不过此时判断右边局部是否是回文串
                if is_palindrome(word, 0, j-1):
                    # 判断右侧局部子串翻转是否在哈希表中
                    right_part_index = find_reversed_word(word, j, word_len-1)
                    if right_part_index != -1 and right_part_index != i:
                        res.append([right_part_index, i])

        return res


words = ["a", ""]
solution = Solution()
solution.palindromePairs(words)

实现后果

欢送关注

公众号【书所集录】