博文中会简要介绍Leetcode P0097题目分析及解题思路。
“Interleaving String”是一道比较有意思的动态规划问题。题目本身其实不算很难，关键在于如何思考和正确地把握题目的关键信息。这道题是一个二维的动态规划，搞清楚dp[i][j]数组的每一维的含义十分重要。
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: trueExample 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false
这道题思路相对比较清晰，重要的是理解interleaving的潜在含义，即s1的前i个字符和s2的前j个字符进行保有原有字符顺序的穿插组合，最终要能构成s3的前i+j个字符。如此理解，递推表达式就很容易得到。
令dp[i][j]表示用s1前i个字符和s2前j个字符组成s3前i+j个字符的可行性，
dp[0][0] = true
显然空串可以组合成空串，
dp[i][0] = dp[i-1][0], if s1[i-1] == s3[i-1]
如果s1[i-1]和s3[i-1]相同，若其前面的字符都相同，则说明s1前i个字符可以组成s3前i个字符，则为可行，反之为不可行，
dp[0][j] = dp[0][j-1], if s2[j-1] == s3[j-1]
同理上述，
dp[i][j] = (dp[i-1][j] && s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s3[i+j-1] == s2[j-1])
简单来说就是，若s3[i+j-1]和s1[i-1]相同，则dp[i][j]的可行性取决于dp[i-1][j]的可行性，即排除s1第i个字符在考虑之外，剩下i-1个字符和s2的前j个字符能否组成s3的前i+j-1个字符。为什么要排除s1的第i个字符在考虑之外呢？原因也很简单，因为s3[i+j-1]与s1[i-1]相同，所以在考虑s3的前i+j-1个字符时，s1的第i个字符已经被匹配给s3的第i+j个字符了，所以不能再使用，但s2的第j个字符并未使用，所以s2要考虑到第j个字符。
以下是Java的题解代码实现。
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len3 = s3.length(), len2 = s2.length(), len1 = s1.length();
if (len3 != len1+len2)
return false;
boolean[][] dp = new boolean[len1+1][len2+1];
char[] chars1 = s1.toCharArray(), chars2 = s2.toCharArray(), chars3 = s3.toCharArray();
// Initialize
dp[0][0] = true;
for (int len=1; len<=len1; ++len) {
dp[len][0] = (chars3[len-1] == chars1[len-1]) && dp[len-1][0];
}
for (int len=1; len<=len2; ++len) {
dp[0][len] = (chars3[len-1] == chars2[len-1]) && dp[0][len-1];
}
// DP
for (int i1=1; i1<=len1; ++i1) {
for (int j2=1; j2<=len2; ++j2) {
dp[i1][j2] = (chars3[i1+j2-1] == chars1[i1-1] && dp[i1-1][j2]) || (chars3[i1+j2-1] == chars2[j2-1] && dp[i1][j2-1]);
}
}
return dp[len1][len2];
}
}
以下是C++的题解代码实现。
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.length(), len2 = s2.length();
if (len1+len2 != s3.length())
return false;
vector<vector<bool>> dp(len1+1, vector<bool>(len2+1, false));
// Initialize
dp[0][0] = true;
for (int idx=1; idx<=len1; ++idx)
dp[idx][0] = (s1[idx-1] == s3[idx-1]) && dp[idx-1][0];
for (int idx=1; idx<=len2; ++idx)
dp[0][idx] = (s2[idx-1] == s3[idx-1]) && dp[0][idx-1];
// DP
for (int i1=1; i1<=len1; ++i1) {
for (int j2=1; j2<=len2; ++j2) {
dp[i1][j2] = (s1[i1-1] == s3[i1+j2-1] && dp[i1-1][j2]) || (s2[j2-1] == s3[i1+j2-1] && dp[i1][j2-1]);
}
}
return dp[len1][len2];
}
};