Leetcode-97.交错字符串

发表于 分类于 阅读次数：

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

示例 1:

输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
输出: true
示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/interleaving-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1：动态规划

1.dp[i][j]表示s1的前i个字符与s2的前j个字符能否组成s3的前i+j个字符串

2.初始化

​ 对于第1列即s2为空dp[i][0]=dp[i-1][0]&&(s1[i-1]==s3[i-1]);

​ 对于第1行即s1为空dp[0][i]=dp[0][i-1]&&(s2[i-1]==s3[i-1]);

3.状态转移方程

​ 两种情况

​ （1）要么是s1[i-1]与s3[i-1+j]结合dp[i][j]=dp[i-1][j]&&(s1[i-1]==s3[i-1+j])

​ （2）要么是s2[j-1]与s3[i+j-1]结合dp[i][j]=dp[i][j-1]&&(s2[j-1]==s3[i+j-1])

4.返回dp[n][m]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.length()+s2.length()!=s3.length())
            return false;
        int n=s1.length(),m=s2.length();
        vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));
        dp[0][0]=true;
        int i,j;
        for(i=1;i<=n;i++)
            dp[i][0]=dp[i-1][0]&&(s1[i-1]==s3[i-1]);
        for(j=1;j<=m;j++)
            dp[0][j]=dp[0][j-1]&&(s2[j-1]==s3[j-1]);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                dp[i][j]=(dp[i-1][j]&&(s1[i-1]==s3[i-1+j])||dp[i][j-1]&&(s2[j-1]==s3[i+j-1]));
            }
        }
        return dp[n][m];
    }
};