给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

  • s = s1 + s2 + … + sn
  • t = t1 + t2 + … + tm
  • |n - m| <= 1
  • 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …

注意：a + b 意味着字符串 a 和 b 连接。

思路

  1. 动态规划，dp[i][j] 维护 s1[:i] 与 s2[:j] 是否满足交错
  2. dp[0][0] = true
  3. dp[i + 1][j] = dp[i][j] && s1[i] === s3[i + j]
  4. dp[i][j + 1] = dp[i][j] && s2[j] === s3[i + j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var isInterleave = function (s1, s2, s3) {
  if (s1.length + s2.length !== s3.length) {
    return false
  }
  const dp = new Array(s1.length + 1).fill(null).map(() => new Array(s2.length + 1).fill(false))
  dp[0][0] = true
  for (let i = 0; i < s1.length; ++i) {
    if (s1[i] !== s3[i]) {
      break
    }
    dp[i + 1][0] = true
  }
  for (let j = 0; j < s2.length; ++j) {
    if (s2[j] !== s3[j]) {
      break
    }
    dp[0][j + 1] = true
  }
  for (let i = 0; i < s1.length; ++i) {
    for (let j = 0; j < s2.length; ++j) {
      dp[i + 1][j + 1] = (dp[i + 1][j] && s2[j] === s3[i + j + 1]) || (dp[i][j + 1] && s1[i] === s3[i + j + 1])
    }
  }
  return dp[s1.length][s2.length]
}

简化空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var isInterleave = function (s1, s2, s3) {
  if (s1.length + s2.length !== s3.length) {
    return false
  }
  const dp = new Array(s2.length + 1).fill(false)
  dp[0] = true
  for (let j = 0; j < s2.length; ++j) {
    if (s2[j] !== s3[j]) {
      break
    }
    dp[j + 1] = true
  }
  for (let i = 0; i < s1.length; ++i) {
    dp[0] = dp[0] && s1[i] === s3[i]
    for (let j = 0; j < s2.length; ++j) {
      dp[j + 1] = (dp[j] && s2[j] === s3[i + j + 1]) || (dp[j + 1] && s1[i] === s3[i + j + 1])
    }
  }
  return dp[s2.length]
}