題目連結:https://leetcode-cn.com/problems/palindrome-pairs/
如果直接每兩個字元串合并,然後去判斷是不是回文串的話,會逾時。
其實可以轉化為比對問題。
設原串為s,那麼将s拆分成s1,s2兩個串,如果s1是回文串,隻需去清單裡找是否存在s2的逆串。
同理 如果s2是回文串,則去找s1的逆串。
快速查找比對字元串的方法就是用字典樹,時間複雜度隻有O(len),len為字元串的長度。
這個題最重要的地方應該是學習一下字典樹。
struct Node
{
int flag;
int ch[26];
Node()
{
flag=-1;
memset(ch,0,sizeof(ch));
}
};
bool isp(string s,int l,int r)
{
//int l =0,r=s.size()-1;
while(l<r)
{
if(s[l]!=s[r]) return false;
l++;
r--;
}
return true;
}
pair<string,string> split(string s,int k)
{
string out1,out2;
for(int i=0;i<k;i++)
{
out1.push_back(s[i]);
}
for(int i=k;i<s.size();i++)
{
out2.push_back(s[i]);
}
return make_pair(out1,out2);
}
class Solution {
public:
vector<Node> tree;
vector<vector<int>> palindromePairs(vector<string>& words) {
tree.push_back(Node());
int n = words.size();
vector<vector<int>> ans;
for(int i=0;i<n;i++)
{
int tmp=insert(words[i],i);
}
for(int i=0;i<n;i++)
{
int len = words[i].size();
for(int k=0;k<=len;k++)
{
if(isp(words[i],k,len-1))
{
int q = query(words[i],0,k-1);
if(q!=-1&&q!=i)
{
vector<int> ve;
ve.push_back(i);
ve.push_back(q);
ans.push_back(ve);
}
}
if(k&&isp(words[i],0,k-1))
{
int q = query(words[i],k,len-1);
if(q!=-1&&q!=i)
{
vector<int> ve;
ve.push_back(q);
ve.push_back(i);
ans.push_back(ve);
}
}
}
}
return ans;
}
int insert(string s,int id)
{
int n = s.size();
int rt=0;
for(int i=0;i<n;i++)
{
int x = s[i]-'a';
if(tree[rt].ch[x]==0)
{
Node tmp;
tree.push_back(tmp);
tree[rt].ch[x] = tree.size()-1;
}
rt = tree[rt].ch[x];
}
tree[rt].flag=id;
return 1;
}
int query(string s,int l,int r)
{
//int l=0,r=s.size()-1;
int rt = 0;
for(int i=r;i>=l;i--)
{
int x = s[i]-'a';
if(tree[rt].ch[x]==0)
{
return -1;
}
rt = tree[rt].ch[x];
}
return tree[rt].flag;
}
};