交错字符串操作

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 <= 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