交错字符串

[louzhedong]

习题

出处：LeetCode 算法第97题

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

思路

字符串问题，多数都可以采用动态规划

解答

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
function isInterleave(s1, s2, s3) {
  if (s1.length + s2.length !== s3.length) {
    return false;
  }

  const length1 = s1.length;
  const length2 = s2.length;
  const dp = [...Array(length1 + 1)].map(r => Array(length2 + 1).fill(false));

  for (let r = 0; r <= length1; r++) {
    for (let c = 0; c <= length2; c++) {
      if (r === 0 && c === 0) {
        dp[r][c] = true;
      } else if (r === 0) {
        dp[r][c] = dp[r][c - 1] && s2[c - 1] === s3[r + c - 1];
      } else if (c === 0) {
        dp[r][c] = dp[r - 1][c] && s1[r - 1] === s3[r + c - 1];
      } else {
        dp[r][c] = (dp[r][c - 1] && s3[r + c - 1] === s2[c - 1]) || (dp[r - 1][c] && s3[r + c - 1] === s1[r - 1]);
      }
    }
  }

  return dp[length1][length2];
}
console.log(isInterleave('aabcc', 'dbbca', 'aadbbcbcac'))