算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 回文对，我们先来看题面：
https://leetcode-cn.com/problems/palindrome-pairs/
Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.
给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
示例 1：
输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2：
输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]]
解释：可拼接成的回文串为 ["battab","tabbat"]
示例 3：
输入：words = ["a",""]
输出：[[0,1],[1,0]]
https://cloud.tencent.com/developer/article/1787956
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string, int> w_id;
set<int> wdLen;
for(int i = 0; i < words.size(); ++i)
{
w_id[words[i]] = i;//字符串idx
wdLen.insert(words[i].size());//字符串长度
}
vector<vector<int>> ans;
string front, back, revword;
for(int i = 0; i < words.size(); ++i)
{
revword = words[i];//逆序的字符串
reverse(revword.begin(),revword.end());
if(w_id.count(revword) && w_id[revword] != i)
ans.push_back({i, w_id[revword]});//字符串的逆序存在
//遍历words[i]可能的子串长度,寻找前部分存在或者后部分存在
//且自身剩余的子串为回文
int len = words[i].size();
for(auto it = wdLen.begin(); *it < len; ++it)
{
front = words[i].substr(0, *it);
reverse(front.begin(),front.end());
back = words[i].substr(*it);
if(w_id.count(front) && ispalind(back))//前缀的逆存在
ans.push_back({i, w_id[front]});
}
for(auto it = wdLen.begin(); *it < len; ++it)
{
front = revword.substr(0, *it);
back = revword.substr(*it);
if(w_id.count(front) && ispalind(back))//后缀的逆存在
ans.push_back({w_id[front], i});
}
}
return ans;
}
bool ispalind(string& s)
{
int l = 0, r = s.size()-1;
while(l < r)
if(s[l++] != s[r--])
return false;
return true;
}
};
class trie
{
public:
unordered_map<char, trie*> next;
int suffix = -1;
void insert(string& s, int idx)
{
trie *cur = this;
for(int i = s.size()-1; i >= 0; --i)//单词逆序插入
{
if(!cur->next[s[i]])
cur->next[s[i]] = new trie();
cur = cur->next[s[i]];
}
cur->suffix = idx;//结束时记录单词编号
}
};
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
trie * t = new trie(), *cur;
vector<vector<int>> ans;
string revword;
for(int i = 0; i < words.size(); ++i)
{
t->insert(words[i], i);
}
for(int i = 0; i < words.size(); ++i)
{
int n = words[i].size(), j, k;
cur = t;
for(j = 0; j < n; ++j)
{
if(cur->suffix != -1 && cur->suffix != i
&& ispalind(words[i], j, n-1))//单词的前缀的逆序在trie中，剩余的为回文
ans.push_back({i, cur->suffix});
if(!cur->next[words[i][j]])
break;
cur = cur->next[words[i][j]];
}
for(j = 0; j <= n; ++j)//等号上下只取一次，否则答案有重复的
{ // j == n 时包含了完整字符串的情况
cur = t;
for(k = n-j; k < n; ++k)//遍历单词的后缀
{
if(!cur->next[words[i][k]])
break;
cur = cur->next[words[i][k]];
}
if(k==n && cur->suffix != -1
&& cur->suffix != i
&& ispalind(words[i], 0, n-j-1))//该后缀的逆在trie中，且前部分为回文
ans.push_back({cur->suffix, i});
}
}
return ans;
}
bool ispalind(string s, int l, int r)
{
while(l < r)
if(s[l++] != s[r--])
return false;
return true;
}
};
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
上期推文：
LeetCode刷题实战325：和等于 k 的最长子数组长度
