# 问题 原题链接：[https://leetcode.com/problems/palindrome-pairs/](https://leetcode.com/problems/palindrome-pairs/) Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome. Example 1: ``` Input: ["abcd","dcba","lls","s","sssll"] Output: [[0,1],[1,0],[3,2],[2,4]] Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"] ``` Example 2: ``` Input: ["bat","tab","cat"] Output: [[0,1],[1,0]] Explanation: The palindromes are ["battab","tabbat"] ``` # 分析过程 - 输入：字符串数组 - 输出：可以两两组成回文的组合下标 - 思路：最简单的是遍历左右可能的组合，拼起来后检查是否是回文，但时间复杂度过高。利用回文的特性，可以针对字符串的子字符串进行分析。 - 组成回文无非一下几种情况： - [ABC][CBA] - [ABC][BA] - [ABCDC][BA] - 他们共同的特征是，在输入的字符串中能够找到这个字符串的某个子串的逆序。 - 只要遍历当前字符串的所有子串，找到这个子串中的回文，然后再在输入中寻找剩余部分的逆序即可。 - 上面提到的回文子串可以是空字符串、一个字母的字符串、或多个字母的回文。 - 需要注意的是，自己不能和自己组成回文，这种情况需要排除。 # 解决方法 ```swift extension String { // 是否是回文 var isPalindrome: Bool { let size = self.count; let startIndex = self.utf8.startIndex for i in 0..<size / 2 { if self.utf8[self.utf8.index(startIndex, offsetBy: i)] != self.utf8[self.utf8.index(startIndex, offsetBy: size - i - 1)] { return false; } } return true; } } class Solution { func palindromePairs(_ words: [String]) -> [[Int]] { // 存放结果 var res = [[Int]]() // 建立存放字符串对应的索引，用于输出 var indexMap = [String: Int]() for (i, str) in words.enumerated() { indexMap[str] = i } // 遍历每个字符串 for i in 0..<words.count { let str = words[i] // 空字符串和其他回文字符串能够拼成回文 guard str != "" else { for k in 0..<words.count { guard k != i else { continue } if words[k].isPalindrome { res.append([i, k]) } } continue } // 拆字符串，以 j 为分界线把字符串拆成两部分 对字符串的每一种分隔方法都遍历 for j in 0..<str.count { let part1 = String(str.prefix(j)) let part2 = String(str.suffix(str.count - j)) // 如果第二部分是回文 if part2.isPalindrome { // 找第一部分的逆序，如果有，拼在第二部分后面即可构成回文 let part1Reversed = String(part1.reversed()) if let index = indexMap[part1Reversed], index != i { res.append([i, index]) } } // 如果第一部分是回文 if part1.isPalindrome { // 找第二部分的逆序，如果有，拼在第一部分前面即可构成回文 let part2Reversed = String(part2.reversed()) if let index = indexMap[part2Reversed], index != i { res.append([index, i]) } } // 这里把空字符串看做是合法回文，对于空子串直接找另一部分的逆序即可 } } return res } } ```