欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

交错字符串操作

程序员文章站 2022-06-22 13:58:11
97. 交错字符串给定三个字符串s1、s2、s3,请你帮忙验证s3是否是由s1和s2交错组成的。输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"输出:true示例 2:输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"输出:false示例 3:输入:s1 = "", s2 = "", s3 = ""输出:true提示:0 &......

97. 交错字符串

给定三个字符串 s1s2s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

 交错字符串操作交错字符串操作

 

输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出:true


示例 2:

输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出:false


示例 3:

输入:s1 = "", s2 = "", s3 = ""
输出:true
 

提示:

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成


基本思路:动态规划,dp[i][j]表示的是由S1的前i个字符和S2的前j个字符是否可以组成S3的前i+j个字符

  • 对于dp[i][j],其最后一个字符,只能是来自于S1的第i个字符,或者S2的第j个字符
  • dp[i][j]=( (s2[j-1]==s3[pos-1]) &&dp[i][j-1] || (s1[i-1]==s3[pos-1]&&dp[i-1][j]) )

注意:该问题类似于路径查找,依照下面的图(来自于leetcode 的sage),且只能向下或者向右,向右相当于选择S2[j],相下相当于选择S1[i],

交错字符串操作

    bool isInterleave(string s1, string s2, string s3) {
        int m=s1.size(),n=s2.size(),k=s3.size();
        if(m+n!=k)
            return false;
        if(m*n==0)
            return s1+s2==s3;
        
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        int pos=0;
        for(int j=1;j<=n&&s3[j-1]==s2[j-1];j++){
            dp[0][j]=1;
        }

        for(int i=1;i<=m&&s3[i-1]==s1[i-1];i++){
            dp[i][0]=1;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                pos=i+j;
                if(s2[j-1]==s3[pos-1]&&dp[i][j-1]){   //只和前面的状态有关,可压缩
                    dp[i][j]=1;
                }
                if(s1[i-1]==s3[pos-1]&&dp[i-1][j]){
                    dp[i][j]=1;
                }
            }
        }
        return dp[m][n];
    }

基本思路:状态压缩

    bool isInterleave(string s1, string s2, string s3) {
        int m=s1.size(),n=s2.size(),k=s3.size();
        if(m+n!=k)
            return false;
        if(m*n==0)
            return s1+s2==s3;
        
        vector<int> dp(n+1,0);
        dp[0]=1;
        for(int j=1;j<=n&&s2[j-1]==s3[j-1];j++)
            dp[j]=1;  //初始化
        
        for(int i=1;i<=m;i++){
            dp[0]=(dp[0]&&s1[i-1]==s3[i-1]);  //注意dp[0]与上一行以及当前的元素有关,要初始化

            for(int j=1;j<=n;j++){
                dp[j]=((dp[j-1]&&s2[j-1]==s3[i+j-1])||(dp[j]&&s1[i-1]==s3[i+j-1]));
            }
        }

        return dp[n];
    }

 

本文地址:https://blog.csdn.net/weixin_40306139/article/details/111122347