intellij idea使用教程 Tomcat 分布式调度 webserver wavedorm 人脸识别 矿工文档 自动化部署 xcode keras webview nhibernate module download scripting tree db2 Way.js vue双向绑定 vue遍历 后台界面模板 后台管理页面模板 jquery对象 ajax的get请求 matlab读取dat文件 mysql当前时间减一天 excel太长的文字隐藏 linux查看mysql进程 collection框架的结构 matlab中axis pip环境变量 matlab停止运行 mysql新增用户和权限 html下拉框默认选中 反函数的二阶导数 python多线程编程 python创建数据库 python基础教程免费 python函数大全 python函数返回
当前位置: 首页 > 学习教程  > 编程语言

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

2021/1/13 20:03:03 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

分割两个字符串得到回文串 给你两个字符串 a 和 b ,它们长度相同。请你选择一个下标,将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串: aprefix 和 asuffix ,满足 a aprefix asuffix ,同理&#xff0…

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

给你两个字符串 a 和 b ,它们长度相同。请你选择一个下标,将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串: aprefix 和 asuffix ,满足 a = aprefix + asuffix ,同理,由 b 可以得到两个字符串 bprefix 和 bsuffix ,满足 b = bprefix + bsuffix 。请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。

当你将一个字符串 s 分割成 sprefix 和 ssuffix 时, ssuffix 或者 sprefix 可以为空。比方说, s = “abc” 那么 “” + “abc” , “a” + “bc” , “ab” + “c” 和 “abc” + “” 都是合法分割。

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

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

示例 1:

输入:a = “x”, b = “y”
输出:true
解释:如果 a 或者 b 是回文串,那么答案一定为 true ,因为你可以如下分割:
aprefix = “”, asuffix = “x”
bprefix = “”, bsuffix = “y”
那么 aprefix + bsuffix = “” + “y” = “y” 是回文串。

示例 2:

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

示例 3:

输入:a = “ulacfd”, b = “jizalu”
输出:true
解释:在下标为 3 处分割:
aprefix = “ula”, asuffix = “cfd”
bprefix = “jiz”, bsuffix = “alu”
那么 aprefix + bsuffix = “ula” + “alu” = “ulaalu” 是回文串。

示例 4:

输入:a = “xbdef”, b = “xecab”
输出:false

提示:

1 <= a.length, b.length <= 105
a.length == b.length
a 和 b 都只包含小写英文字母

题解:

比较有趣的题目,我将字符串分为3段,也就是
a=a1+a2+a3;
b=b1+b2+b3;
其中保证a1.length()=a3.length(),b1.length()=b3.length(),因为题目要求同样的下标进行分割,于是a1.length()=b1.length()。
如果a1等于b3,意味着可以得到一个新的字符串s=a1+a2+b3。因为a1等于b3,此时再满足a2是一个回文串,那么s就是回文串,也就意味者按题目的意思进行操作可以构成回文串。

可以发现,a2就是从字符串a中间向两边进行拓展得到的回文串,假设a2的左下标为self_pos1,并且a1和b3相同,而且长度为common_len1,如果self_pos1<=common_len1,就说明可以构成字符串,因为多余的部分都是回文串内容。

AC代码

class Solution {
public:
    int get_common_length(string a,string b)//求a的前缀和b的后缀的共同长度
    {
        int ans=0;
        int n=a.length();
        for(int i=0;i<n;i++)
        {
            if(a[i]!=b[n-i-1])break;
            ans++;
        }
        return ans;
    }
    int get_self_length(string s)//得到字符串s以中间位置向两边拓展能得到的最大回文串长度
    {
        int n=s.length();
        int st,et;
        if(n%2==0)
        st=n/2,et=n/2-1;
        else
        {
            st=et=n/2;
        }
        int pos=st;
        for(int i=st,j=et;i>=0;i--,j++)
        {
            if(s[i]!=s[j])break;
            pos=i;
        }
        return pos;
    }
    bool checkPalindromeFormation(string a, string b) {
        int common_len1=get_common_length(a,b);
        int common_len2=get_common_length(b,a);
        int self_pos1=get_self_length(a);
        if(self_pos1<=common_len1||self_pos1<=common_len2)//判断是否可替换
        return true;
        int self_pos2=get_self_length(b);
        if(self_pos2<=common_len1||self_pos2<=common_len2)//判断是否可替换
        return true;
        return false;
    }
};

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_600242.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?