leetcode-336. 回文对

本文主要是介绍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"]

解题思路

暴力版：从前向后遍历，判断2个字符串可不可以拼接后回文。
时间复杂度$o(n^2\ast m)$，m是输入数据中每个字符串的长度，超时了

看了官方题解才想到的：
假如s1, s2能拼接成回文串，对于较长的字符串（假设是s1）来说，必然可以将s1分成2个部分t1, t2，其中，t1是s2的反转，t2本身就是一个回文串

所以先保存一个字符串反转后的字典，然后对每个字符串，找出内含的回文串，看看剩下的部分有没有反转的字符串和它对应即可。

时间复杂度是$o(n\ast m^2)$，其中m是每个字符串的长度

代码

暴力版：

class Solution:def palindromePairs(self, words: List[str]) -> List[List[int]]:ans = []for i in range(len(words) - 1):for j in range(i + 1, len(words)):concate_word = words[i] + words[j]if concate_word == concate_word[::-1]:ans.append((i, j))concate_word = words[j] + words[i]if concate_word == concate_word[::-1]:ans.append((j, i))return ans

优化版：

class Solution:def palindromePairs(self, words: List[str]) -> List[List[int]]:reverse_dict = {}for index, word in enumerate(words):reverse_dict[word[::-1]] = indexans = []for index, each_word in enumerate(words):for word_index in range(len(each_word) + 1):left_word = each_word[:word_index]right_word = each_word[word_index:]# attach rightif right_word == right_word[::-1]:if left_word in reverse_dict and index != reverse_dict[left_word]:ans.append((index, reverse_dict[left_word]))# attach leftif left_word == left_word[::-1]:if right_word in reverse_dict and index != reverse_dict[right_word]:ans.append((reverse_dict[right_word], index))return list(set(ans))

这篇关于leetcode-336. 回文对的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---