LeetCode 97. 交错字符串

题目描述

✅ 97. 交错字符串

考察公司：美团

考察时间：2025.5.28

image-20250528202233985

image-20250528202306724

image-20250528202353379

思路分析

dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交错组成 s3 的前 i + j 个字符。

image-20250528205702476

参考代码



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
26



func isInterleave(s1 string, s2 string, s3 string) bool {
	if len(s1)+len(s2) != len(s3) {
		return false
	}

	m, n := len(s1), len(s2)
	dp := make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true

	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			if i > 0 && s1[i-1] == s3[i+j-1] {
				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]
}
  • 时间复杂度：O(m * n)，我们需要遍历整个 dp 数组，其中 m 和 n 分别是 s1 和 s2 的长度。
  • 空间复杂度：O(m * n)，我们使用了一个 m * n 的二维数组来存储状态。

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/35539364
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！