跳至主要內容

97. 交错字符串


97. 交错字符串open in new window

🟠   🔖  字符串 动态规划  🔗 力扣open in new window LeetCodeopen in new window

题目

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Output: true

Explanation: One way to obtain s3 is:

Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".

Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".

Since s3 can be obtained by interleaving s1 and s2, we return true.

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

Output: false

Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.

Example 3:

Input: s1 = "", s2 = "", s3 = ""

Output: true

Constraints:

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1, s2, and s3 consist of lowercase English letters.

Follow up: Could you solve it using only O(s2.length) additional memory space?

题目大意

给定三个字符串 s1s2s3,请判断 s3 能不能由 s1s2 交织(交错) 组成。

两个字符串 st 交织 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串:

  • 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 意味着字符串 ab 连接。
  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1s2、和 s3 都由小写英文字母组成

进阶: 您能否仅使用 O(s2.length) 额外的内存空间来解决它?

解题思路

思路一:动态规划

  1. 动态规划

    • 使用一个二维布尔数组 dp,其中 dp[i][j] 表示 s3 的前 i + j 个字符可以由 s1 的前 i 个字符和 s2 的前 j 个字符交错形成。
  2. 状态转移

    • 初始化 dp[0][0]true,表示空字符串可以由两个空字符串交错形成。
    • 然后填充 dp 表:
      • 如果 s1[i-1]s3[i+j-1] 相等,则 dp[i][j] 可以从 dp[i-1][j] 转移而来。
      • 如果 s2[j-1]s3[i+j-1] 相等,则 dp[i][j] 可以从 dp[i][j-1] 转移而来。
  3. 最终结果

    • dp[s1.length][s2.length] 表示 s3 是否可以由 s1s2 交错形成。

复杂度分析

  • 时间复杂度O(m * n),需要填充整个 dp 数组。
  • 空间复杂度O(m * n),使用的 DP 数组。

思路二:动态规划+压缩状态

要通过使用一维数组代替二维数组,可以将思路一的空间复杂度优化到 O(n)

  • 我们只需要保留当前行的信息,因此可以用一个长度为 n + 1 的一维数组来存储状态。
  • 创建一个长度为 n + 1 的一维数组 dp,并初始化 dp[0]true
  • 处理 s2 的字符,初始化 dp 的第一行。
  • 处理 s1 的字符,更新 dp 数组。
  • 在更新时,从后向前更新,以防止覆盖之前的数据。使用当前 dp[j]dp[j - 1] 来判断是否可以交错形成 s3 的相应部分。

复杂度分析

  • 时间复杂度O(m * n),与之前相同。
  • 空间复杂度O(n),通过使用一维数组代替二维数组来减少空间使用。

总结:

代码

动态规划
/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function (s1, s2, s3) {
	const m = s1.length,
		n = s2.length;

	if (m + n !== s3.length) return false;

	let dp = new Array(m + 1).fill(0).map((i) => new Array(n + 1).fill(false));
	dp[0][0] = true;

	for (let i = 0; i <= m; i++) {
		for (let j = 0; j <= n; j++) {
			if (i > 0 && s1[i - 1] == s3[i - 1 + j]) {
				dp[i][j] = dp[i][j] || dp[i - 1][j];
			}
			if (j > 0 && s2[j - 1] == s3[i + j - 1]) {
				dp[i][j] = dp[i][j] || dp[i][j - 1];
			}
		}
	}

	return dp[m][n];
};