LeetCode|LeetCode 336. 回文对 | Python LeetCode336.回文对|Python

336. 回文对题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/palindrome-pairs
题目给定一组唯一的单词，找出所有不同的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j]，可拼接成回文串。
【LeetCode|LeetCode 336. 回文对 | Python】示例 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。根据示例，我们来分情况进行分析：

当 a_len = b_len 时，那么 a 一定是 b 的翻转；
当 a_len > b_len 时，由于 b 的长度较小，那么这个时候要组成回文串，a 中肯定有部分已经是回文串。那么将 a 划分为前后 a1 和 a2 两部分，前面 a1 部分是 b 的翻转，而 a2 自身是回文串；
当 a_len < b_len 时，这个情况其实是上面一种的反面。同样将 b 划分为前后 b1 和 b2 两个部分，b1 自身是回文串，而 b2 是 a 的翻转。

从上面的分析，我们可以发现，拆解的都是长度较长的字符串。那么，我们现在可以尝试枚举每个字符串 i，将其认为是较长的字符串，那么我们现在将其拆分 i1 和 i2。那么这里将会有两种情况：

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

在这里，需要注意一种情况，也就是空字符串。因为空字符串也是回文串。那么上面的拆解过程中，当将字符串 i 拆解后，其中 i1 和 i2 某一个为空串时，这种情况其实就符合前面所分析的第一种情况。
那么现在需要主要的就是，如何判断拆分后的子串的翻转子串在给定的字符串列表中是否存在？
这里可以考虑使用哈希表来存储所有字符串的翻转字符串。那么在查询的拆分后的子串时，只要判断其是否在哈希表中，就能得到结果。
具体的代码实现如下。
代码实现

from typing import Listclass 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] = ires = []# 遍历字符串，拆分字符串，进行判断 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 reswords = ["a", ""] solution = Solution() solution.palindromePairs(words)

实现结果