LeetCode 97. 交错字符串

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 97. 交错字符串

考察公司：美团

考察时间：2025.5.28

思路分析

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

参考代码

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 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/35539364