力扣每日一题3.18（字符串匹配）

你好旅行者!欢迎来到cyt的练功房。本篇文章来记录一下力扣的2023.3.18的每日一题，这个好像传统的字符串匹配$O_{n^2}$ 做不出来，就学了一下$O_{n}$ 记录一下 。

1616. 分割两个字符串得到回文串

给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串： $a_{prefix}$ 和 $a_{suffix}$ ，满足 a = $a_{prefix}$ + $a_{suffix}$ ，同理，由 b 可以得到两个字符串 $b_{prefix}$ 和 $b_{suffix}$ ，满足 b = $b_{prefix}$ + $b_{suffix}$ 。请你判断 $a_{prefix}$ + $b_{suffix}$ 或者 $b_{prefix}$ + $a_{suffix}$ 能否构成回文串。

当你将一个字符串 s 分割成 $s_{prefix}$ 和 $s_{suffix}$$s_{suffix}$ 或者 $s_{prefix}$ 可以为空。比方说， s = “abc” 那么 “” + “abc” ， “a” + “bc” ， “ab” + “c” 和 “abc” + “” 都是合法分割。

如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。

注意， x + y 表示连接字符串 x 和 y 。

输入：a = “abdef”, b = “fecab”
输出：true

容易想到的思路是取每一个分割时的字符串，将两个字符串记录下来，判断是否是回文序列，看了一眼范围10^5，应该是过不了的，但是还是试了一下

class Solution {
public:
    bool check(string &s){
        int begin=s.size()/2;
        int left,right;
        // 如果字符串的长度是奇数
        if(s.size()%2){
            left=begin-1;right=begin+1;
            while(left>=0&&right<=s.size()-1){
                if(left<0||right>s.size()-1)break;
                if(s[left]!=s[right]){
                    return false;
                }
                left--;
                right++;
            }
        }else{
            // 如果字符串的长度是偶数
            // cout<<11111111<<endl;
            left=begin-1;right=begin;
            while(left>=0&&right<=s.size()-1){
                if(left<0||right>s.size()-1)break;
                if(s[left]!=s[right]){
                    return false;
                }
                left--;
                right++;
            }
        }
        return true;
    }
    bool checkPalindromeFormation(string &a, string &b) {
        int n=a.size();
        string res1,res2;
        if(check(a)||check(b)){
            return true;
        }
        for(int i=0;i<a.size();i++){
            // 遍历所有可以形成的字符串
            res1="",res2="";
            res1=res1+a.substr(0,i)+b.substr(i,n-i);
            res2=res2+b.substr(0,i)+a.substr(i,n-i);
            if(check(res1)||check(res2)){
                return true;
            }
        }
        return false;

    }
};

跑了一下，果然超时了 QAQ只能在想点别的办法了。
想想$O_{n}$的做法呃，先匹配两个字符串的最长前后缀，如果没有前后缀的话怎么也不可能成为回文的序列，再看剩下的中间部分有没有回文序列，如果有就找到了，没有就没有。

class Solution {
public:
    bool check(string &s){
        int begin=s.size()/2;
        int left,right;
        // 如果字符串的长度是奇数
        if(s.size()%2){
            left=begin-1;right=begin+1;
            while(left>=0&&right<=s.size()-1){
                if(left<0||right>s.size()-1)break;
                if(s[left]!=s[right]){
                    return false;
                }
                left--;
                right++;
            }
        }else{
            // 如果字符串的长度是偶数
            // cout<<11111111<<endl;
            left=begin-1;right=begin;
            while(left>=0&&right<=s.size()-1){
                if(left<0||right>s.size()-1)break;
                if(s[left]!=s[right]){
                    return false;
                }
                left--;
                right++;
            }
        }
        return true;
    }
    bool checkPalindromeFormation(string &a, string &b) {
        int n=a.size();
        string res1,res2;
        int begin=0,end=b.size()-1;
        // 匹配最长前缀后缀
        while(a[begin]==b[end]&&begin<end){
            begin++;end--;
        }
        int begin1=0,end1=b.size()-1;
        while(b[begin1]==a[end1]&&begin1<end1){
            begin1++;end1--;
        }
        if(begin1>begin){
            begin=begin1;
            end=end1;
        }
        if(begin>=end)return true;
        res1=a.substr(begin,end-begin+1),res2=b.substr(begin,end-begin+1);
        return check(res1)||check(res2);


    }
};

需要注意的是要whlie两侧，一侧是a开始，一侧是b开始。

嗯~ o(￣▽￣)o 今天的每日一题完成了！！！又学到了很多