思路：要看两个字符串str1和str2连接是否为回文串，有两种情况。
第一种：str1的后半部分本身构成了回文串，这时候只要看str1的前半部分是否和str2的翻转字符串是否匹配。例如：str1: abcdxyx, str2: dcba. str1 + str2构成回文串
第二种，str1的前半部分构成了回文串，这时候只要看str1的后半部分是否和str2的翻转字符串是否匹配。例如： str1: xyxabcd, str2: dcba. str2 + str1构成回文串。
因此，首先将所有的字符串翻转后插入到Trie树中。flag标记每个单词的位置。
每次判断一个单词是否能够与其他单词构成回文串时，遍历前半部分字符串的长度，如果后半部分构成回文串并且前半部分能够在Trie中找到，并且位置不等于自己的位置，那么形成一个回文对。同样判断第二种情况。
复杂度：O (N * L * L) N为单词个数，L为最长单词长度。
C++代码：
class Solution {
public:
int tree[100010][30];
int tot = 1;
int flag[100010];
void insert(string str, int pos){
int root = 0;
for(int i = str.size() - 1; i >= 0; i--){
int id = str[i] - 'a';
if(tree[root][id] == -1){
tree[root][id] = tot++;
}
root = tree[root][id];
}
flag[root] = pos;
}
int find(string str, int pos){
int root = 0;
for(int i = 0; i < str.size(); i++){
int id = str[i] - 'a';
if(tree[root][id] == -1){
return -1;
}
root = tree[root][id];
}
if(flag[root] != -1 && flag[root] != pos){
return flag[root];
}
return -1;
}
bool judge(string str){
int l = 0, r = str.size() - 1;
while(l <= r){
if(str[l] != str[r]) return false;
l++;
r--;
}
return true;
}
vector<vector<int>> palindromePairs(vector<string>& words) {
memset(flag, -1, sizeof(flag));
memset(tree, -1, sizeof(tree));
for(int i = 0; i < words.size(); i++){
insert(words[i], i);
}
vector<vector<int>> resvec;
for(int i = 0; i < words.size(); i++){
for(int j = 0; j <= words[i].size(); j++){
string left = words[i].substr(0, j);
string right = words[i].substr(j);
if(j > 0 && judge(left)){
int pos = find(right, i);
cout << left << " " << right << " " << pos << endl;
if(pos != -1 && pos != i){
resvec.push_back(vector<int>{pos, i});
}
}
if(judge(right)){
int pos = find(left, i);
cout << left << " " << right << " " << pos << endl;
if(pos != -1 && pos != i){
resvec.push_back(vector<int>{i, pos});
}
}
}
}
return resvec;
}
};
网友评论