题目内容

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

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …

提示：a + b 意味着字符串 a 和 b 连接。

示例

示例 1：

输入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
输出：true

示例 2：

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

示例 3：

输入：s1 = “”, s2 = “”, s3 = “”
输出：true

提示

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

题解

本题采用动态规划的思路求解。

1、状态表示F[i,j]，表示所有由S1[1,i]和S2[1,j]交错形成S3[1,i+j]的方案，内部值代表集合是否非空，即存储布尔值。

2、状态计算，观察S3最后一个字符的归属：

（1）当最后一个字符属于S1，F[i,j] = F[i-1,j]

（2）当最后一个字符属于S2，F[i,j] = F[i,j-1]

代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size(),m = s2.size();
        if(s3.size() != n + m) return false;

        vector<vector<bool>> f(n+1,vector<bool>(m+1));

        s1 = ' '+ s1,s2 = ' '+s2,s3 = ' '+s3;
        for(int i = 0;i <= n;i++)
            for(int j = 0;j<=m;j++)
                if(!i && !j) f[i][j] = true;
                else{
                    if(i && s1[i] == s3[i+j]) f[i][j] = f[i-1][j];
                    if(j && s2[j] == s3[i+j]) f[i][j] = f[i][j]||f[i][j-1];//这里用或运算是因为在S1[i] == S3[i+j]的情况下，f[i][j]被更新，因此就算f[i][j-1]为false，也保留了前一种情况的结果。例如第一种情况是true，但是第二种情况为false，但是呢总体的f[i][j]应该为true而不是false，因此用或运算就解决了这个问题。
                }
        return f[n][m];
    }
};