LeetCode 336. 回文对

Bertha 。 2022-11-29 14:29 161阅读 0赞

题目链接：[https://leetcode-cn.com/problems/palindrome-pairs/][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;
    }
        
    };

[https_leetcode-cn.com_problems_palindrome-pairs]: https://leetcode-cn.com/problems/palindrome-pairs/