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"]

题解

我们用一个哈希表记录出现的字符串，以及下标 构成回文串有以下几种可能

本身是回文串，和空串进行拼接。这种情况下，空串可以拼接在任意一端不共用任何部分，单纯两个串进行拼接。这种情况，我们需要reverse字符串，如果找到，则进行拼接，拼接到后面共用当前字符串的前一部分。这种情况，我们需要reverse字符串的后一部分，也就是不共用部分，如果找到，则进行拼接，拼接到前面共用当前字符串的后一部分。这种情况，我们需要reverse字符串的前一部分，也就是不共用部分，如果找到，则进行拼接，拼接到后面 详细过程见代码

代码

bool isReverseStr(string& str){ //判断是否为回文串 int len = str.length(); int i=0,j=len-1; while(i < j){ if(str[i] == str[j]){ i++; j--; }else return false; } return true; } string reverseStr(string& str,int i,int j){ //将str[i~j]进行反转 string ans; for(; j>=i; j--) ans += str[j]; return ans; } vector<vector<int>> palindromePairs(vector<string>& words) { unordered_map<string,int> wordsIndex; int n = words.size(); for(int i=0; i<n; i++){ wordsIndex[words[i]] = i; } vector<vector<int>> ans; for(int i=0; i<n; i++){ if(words[i] == "") continue; if(isReverseStr(words[i]) && wordsIndex.count("")!=0){ //本身是回文，那么和它拼接的可以是空串 ans.push_back({i,wordsIndex[""]}); ans.push_back({wordsIndex[""],i}); } int len = words[i].length(); string rev = reverseStr(words[i],0,len-1); if(rev!=words[i] && wordsIndex.count(rev)!=0) //找无共用字母的回文串 ans.push_back({i,wordsIndex[rev]}); for(int j=1; j<len; j++){ string now = words[i].substr(0,j); //找共用word[i][0~j-1]的回文串 if(isReverseStr(now)){ //共用部分需要保证是回文串 string subRev = reverseStr(words[i],j,len-1); if(wordsIndex.count(subRev) != 0){ ans.push_back({wordsIndex[subRev],i}); } } } for(int j=1; j<len; j++){ string now = words[i].substr(j); //找共用word[i][j~len-1]的回文串 if(isReverseStr(now)){ //共用部分需要保证是回文串 string subRev = reverseStr(words[i],0,j-1); if(wordsIndex.count(subRev) != 0){ ans.push_back({i,wordsIndex[subRev]}); } } } } return ans; }

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-pairs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。