1.题目解析
题目来源
97.交错字符串——力扣
测试用例
2.算法原理
1.状态表示
这里需要判断能否可以使用s1与s2来交错组成s3，所以不妨将s1与s2分为两个区间，这样的话s3就是s1与s2区间长度的和，这里将三个字符串开头均加上空格可以使下标映射更加简单，即
dp[i][j]：s1的[1,i]区间与s2的[1,j]区间是否可以交错组成s3的[1,i+j]区间
2.状态转移方程
状态转移方程这里使用s1与s2的末尾与s3的末尾作对比来进行填表，详细解析如下：
3.初始化
这里引入了空字符串进行虚拟位置的初始化，下图就是对虚拟位置初始化的详细解析
4.填表顺序
从左到右，每一行从上到下
5.返回值
从状态表示可知只需要返回dp表的最后一个位置dp[m][n]即可
3.实战代码
代码解析
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int m = s1.size();int n = s2.size();vector<vector<bool>> dp(m+1,vector<bool>(n+1));if(m + n != s3.size()){return false;}s1 = " " + s1,s2 = " " + s2, s3 = " " + s3;dp[0][0] = true;for(int i = 1;i <= m;i++){if(s1[i] == s3[i]){dp[i][0] = true;}else {break;}} for(int j = 1;j <= n;j++){if(s3[j] == s2[j]){dp[0][j] = true;}else {break;}} for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){dp[i][j] = (s1[i] == s3[i+j] && dp[i-1][j])|| (s2[j] == s3[i+j] && dp[i][j-1]);}}return dp[m][n];}
};
