1. 题⽬链接：97.交错字符串
2. 题⽬描述：
3. 解法（动态规划）：
算法思路：
对于两个字符串之间的dp 问题，我们⼀般的思考⽅式如下：
i. 选取第⼀个字符串的[0, i] 区间以及第⼆个字符串的[0, j] 区间当成研究对象，结合题⽬的要求来定义「状态表⽰」；
ii. 然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移 ⽅程」。 我们可以根据上⾯的策略，解决⼤部分关于两个字符串之间的dp 问题。
这道题⾥⾯空串是有研究意义的，因此我们先预处理⼀下原始字符串，前⾯统⼀加上⼀个占位符： s1 = " " + s1, s2 = " " + s2, s3 = " " + s3 。
1. 状态表⽰：
dp[i][j] 表⽰字符串s1 中[1, i] 区间内的字符串以及s2 中[1, j] 区间内的字符串，能否拼接成s3 中[1, i + j] 区间内的字符串。
2. 状态转移⽅程：
先分析⼀下题⽬，题⽬中交错后的字符串为s1 + t1 + s2 + t2 + s3 + t3...... ，看 似⼀个s ⼀个t 。实际上s1 能够拆分成更⼩的⼀个字符，进⽽可以细化成s1 + s2 + s3 + t1 + t2 + s4...... 。 也就是说，并不是前⼀个⽤了s 的⼦串，后⼀个必须要⽤t 的⼦串。这⼀点理解，对我们的状 态转移很重要。 继续根据两个区间上「最后⼀个位置的字符」，结合题⽬的要求，来进⾏「分类讨论」：
i. 当s3[i + j] = s1[i] 的时候，说明交错后的字符串的最后⼀个字符和s1 的最后⼀ 个字符匹配了。那么整个字符串能否交错组成，变成： s1 中[1, i - 1] 区间上的字符串以及s2 中[1, j] 区间上的字符串，能够交 错形成s3 中[1, i + j - 1] 区间上的字符串，也就是dp[i - 1][j] ；此时dp[i][j] = dp[i - 1][j]
ii. 当s3[i + j] = s2[j] 的时候，说明交错后的字符串的最后⼀个字符和s2 的最后 ⼀个字符匹配了。那么整个字符串能否交错组成，变成： s1 中[1, i] 区间上的字符串以及s2 中[1, j - 1] 区间上的字符串，能够交 错形成s3 中[1, i + j - 1] 区间上的字符串，也就是dp[i][j - 1] ；
iii. 当两者的末尾都不等于s3 最后⼀个位置的字符时，说明不可能是两者的交错字符串。
上述三种情况下，只要有⼀个情况下能够交错组成⽬标串，就可以返回true 。因此，我们可以 定义状态转移为： dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]) 只要有⼀个成⽴，结果就是true 。
3. 初始化：
由于⽤到i - 1 ,j - 1 位置的值，因此需要初始化「第⼀个位置」以及「第⼀⾏」和「第⼀ 列」。
◦ 第⼀个位置： dp[0][0] = true ，因为空串+空串能够构成⼀个空串。
◦ 第⼀⾏： 第⼀⾏表⽰s1 是⼀个空串，我们只⽤考虑s2 即可。因此状态转移之和s2 有关： dp[0][j] = s2[j - 1] == s3[j - 1] && dp[0][j - 1] ， j 从1 到n （ n 为s2 的⻓度）
◦ 第⼀列： 第⼀列表⽰s2 是⼀个空串，我们只⽤考虑s1 即可。因此状态转移之和s1 有关： dp[i][0] = s1[i - 1] == s3[i - 1] && dp[i - 1][0] ， i 从1 到m （ m 为s1 的⻓度）
4. 填表顺序：
根据「状态转移」，我们需要「从上往下」填每⼀⾏，每⼀⾏「从左往右」。
5. 返回值：
根据「状态表⽰」，我们需要返回dp[m][n] 的值。
C++算法代码：
class Solution
{
public:
bool isInterleave(string s1, string s2, string s3)
{
int m=s1.size(),n=s2.size();
//优化
if(m+n!=s3.size())
{
return false;
}
s1=" "+s1;
s2=" "+s2;
s3=" "+s3;
//建表
vector<vector<bool>>dp(m+1,vector<bool>(n+1));
//初始化
dp[0][0]=true;
for(int i=1;i<=m;i++)
{
if(s1[i]!=s3[i])
{
break;
}
dp[i][0]=true;
}
for(int i=1;i<=n;i++)
{
if(s2[i]!=s3[i])
{
break;
}
dp[0][i]=true;
}
//填表
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];
}
};Java算法代码：
class Solution
{
public boolean isInterleave(String s1, String s2, String s3)
{
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) return false; // 处理下边界条件
s1 = " " + s1; s2 = " " + s2; s3 = " " + s3;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true; // 初始化
for (int j = 1; j <= n; j++) // 初始化第⼀⾏
if (s2.charAt(j) == s3.charAt(j)) dp[0][j] = true;
else break;
for (int i = 1; i <= m; i++) // 初始化第⼀列
if (s1.charAt(i) == s3.charAt(i)) dp[i][0] = true;
else break;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = (s1.charAt(i) == s3.charAt(i + j) && dp[i - 1][j])
|| (s2.charAt(j) == s3.charAt(i + j) && dp[i][j - 1]);
return dp[m][n];
}
}