判断s3是否由s1和s2交织组成，动态规划求解，faster than 71%
dp[i - 1][j] == true && s1.charAt(i - 1) === s3.charAt(i + j - 1)
dp[i][j - 1] == true && s2.charAt(j - 1) === s3.charAt(i + j - 1)
dp[i][j] = true 表示s1的前i个字符与s2的前j个字符可以交织组成s3的i + j 个字符
即s1的前i - 1个字符与s2的前j个字符可以交织组成s3的i + j 个字符，若s1的第 i - 1个字符与s3的前 i + j - 1个字符相等，这个多1是考虑空字符串的情况。
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function(s1, s2, s3) {
const m = s1.length + 1;
const n = s2.length + 1;
if (m + n !== s3.length + 2) {
return false;
}
const dp = new Array(m).fill().map(i => Array(n).fill(false));
dp[0][0] = true;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if ((i > 0 && dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) || (j > 0 && dp[i][j - 1] && s2[j - 1] === s3[i + j - 1])) {
dp[i][j] = true;
}
}
}
return dp[m - 1][n - 1];
};
使用滚动数组优化空间复杂度，数组的第i行只和i-1行相关，可以对使用空间进行优化。
- 时间复杂度O(mn)，空间复杂度O(1)
- Runtime: 76 ms, faster than 92.54%
- Memory Usage: 40 MB, less than 91.79%
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function(s1, s2, s3) {
const m = s1.length + 1;
const n = s2.length + 1;
if (m + n !== s3.length + 2) {
return false;
}
const dp = [];
dp[0] = true;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i > 0) {
dp[j] = (dp[j] && (s1[i - 1] === s3[i + j - 1]));
}
if (j > 0) {
dp[j] = dp[j] || (dp[j - 1] && s2[j - 1] === s3[i + j - 1]);
}
}
}
return dp[n - 1];
};
