97 Interleaving String

判断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];
};