企业官网建设流程全解析

LeetCode-Go：用记忆化 DFS 求解 LeetCode 97 交错字符串的完整解析

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇以 LeetCode-Go 仓库中《LeetCode Cookbook》第 97 题（Interleaving String，交错字符串）的题解文档为主体，完整继承原题的定义、示例与约束条件，并结合仓库中的 Go 实现与测试文件，逐层拆解"状态空间 + 记忆化深搜"的解法原理、一维状态编码技巧、边界剪枝与复杂度分析，读完后你能掌握这类二维匹配类字符串问题从暴力深搜到记忆化搜索的完整工程化实现路径。

一、题目定义与形式化描述

给定三个字符串s1、s2、s3，判断s3是否由s1与s2交错（interleaving）组成。题解文档 0097.Interleaving-String.md 给出了交错的形式化定义：两个字符串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的连接。

题目给出的三个官方示例：

约束条件：

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1、s2、s3均由小写英文字母组成
• Follow up：能否只用O(s2.length)的额外空间解决？

仓库中该题的中文版题解见 README.md，与英文版题解内容一致，中文表述为："给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的"。

二、状态空间建模：为什么判断位置是 s3[p1+p2]

理解这道题的关键，是把"交错匹配"转化为在二维状态网格上找一条路径的过程：

• 设p1为s1当前已匹配的字符数（即s1的下一个待比较下标），p2为s2的对应下标；
• 当已经匹配了p1个字符来自s1、p2个字符来自s2时，s3中下一个必须匹配的字符位置恰好是s3[p1+p2]——因为s3的前缀已经由两部分按顺序拼出了p1+p2个字符；
• 从状态(p1, p2)出发，只有两种合法转移：
  • 若s3[p1+p2] == s1[p1]，可转移到(p1+1, p2)；
  • 若s3[p1+p2] == s2[p2]，可转移到(p1, p2+1)。

起点是(0, 0)，终点是(len(s1), len(s2))。问题等价于：在(len(s1)+1) × (len(s2)+1)的状态网格中，是否存在一条沿右/下方向走到右下角的路径。题解文档原文明确指出："因为是交错字符串，所以判断匹配的位置是 s3[p1+p2] 的位置"，这正是该二维建模的直接推论。

如果仅按上述规则做朴素深搜，题解文档同样指出"会超时，s1 和 s2 两个字符串重复交叉判断的位置太多了"——因为到达同一状态(p1, p2)的路径数量是指数量级的（任意先走几步、后走几步的组合），大量状态会被反复探索。因此必须引入记忆化。

三、仓库中的核心实现：记忆化 DFS 全解析

仓库实现位于 97. Interleaving String.go，共 35 行，完整代码如下：

package leetcode func isInterleave(s1 string, s2 string, s3 string) bool { if len(s1)+len(s2) != len(s3) { return false } visited := make(map[int]bool) return dfs(s1, s2, s3, 0, 0, visited) } func dfs(s1, s2, s3 string, p1, p2 int, visited map[int]bool) bool { if p1+p2 == len(s3) { return true } if _, ok := visited[(p1*len(s3))+p2]; ok { return false } visited[(p1*len(s3))+p2] = true var match1, match2 bool if p1 < len(s1) && s3[p1+p2] == s1[p1] { match1 = true } if p2 < len(s2) && s3[p1+p2] == s2[p2] { match2 = true } if match1 && match2 { return dfs(s1, s2, s3, p1+1, p2, visited) || dfs(s1, s2, s3, p1, p2+1, visited) } else if match1 { return dfs(s1, s2, s3, p1+1, p2, visited) } else if match2 { return dfs(s1, s2, s3, p1, p2+1, visited) } else { return false } }

下面按执行顺序拆解各部分的设计意图。

3.1 长度前置剪枝：最便宜的失败判定

入口函数 isInterleave 第一行就检查len(s1)+len(s2) != len(s3)。交错不改变字符总数，因此长度不等可以直接判负，无需进入搜索。这条剪枝在官方约束下覆盖了s3.length最大 200 而s1、s2各最大 100 的边界情形，也解释了测试文件中为什么会出现一个"长度对不上"的用例（见第四节）。

3.2 终止条件与递归推进

dfs 的第一条判断是p1+p2 == len(s3)即返回true。结合前置剪枝可知：既然总长度相等，s3被完全消耗时s1与s2必然也恰好用完（若某一侧提前耗尽，match1/match2会在越界检查处被置为false，最终落入else分支返回false），因此不必再单独比较p1 == len(s1) && p2 == len(s2)。

两侧匹配判定均带有越界保护：p1 < len(s1) && s3[p1+p2] == s1[p1]。当s1已耗尽而s2未耗尽时，只剩单条转移边，搜索退化为线性的"一路走到头"。

3.3 记忆化的一维编码：p1 * len(s3) + p2 为什么是唯一下标

题解文档的核心思想是用visited[i][j]二维结构记录状态是否已搜索，而实现中做了一个空间压缩——把二维状态编码进一维整数键：

if _, ok := visited[(p1*len(s3))+p2]; ok { return false } visited[(p1*len(s3))+p2] = true

该编码的数学依据是：状态p2的合法取值范围是[0, len(s2)]，必然满足p2 < len(s2) <= len(s3)（由前置剪枝len(s1)+len(s2) == len(s3)可知len(s2) < len(s3)，除非s1为空），而p1 <= len(s1) <= len(s3)。因此p1*len(s3) + p2是以len(s3)为"行宽"的行列展开式：不同(p1, p2)对产生的值互不冲突，与 Go 中把二维数组拍平为一维索引的经典做法（idx = i*cols + j）完全一致。由于该函数运行于go 1.19的 Go module 环境（见 go.mod），int为 64 位，在本题约束下（p1*200+200 < 40000）也不存在任何溢出风险。

从源码结构看，这里用map[int]bool而非[m+1][n+1]bool数组，是典型的"稀疏访问"取舍：实际被访问的状态数往往远小于网格总面积，map 只为真正到达过的状态分配条目；代价是每次查询有一次哈希开销，但状态转移本身是 O(1)，整体复杂度不变。

3.4 "进入即标记"的正确性

值得注意的是，visited标记发生在进入状态时而非"搜索完毕确认无解时"，重访已标记状态直接返回false。这一写法看似激进，但在本题中是安全的：由于每次转移都会使p1+p2严格 +1，状态图是严格前进的 DAG，不存在环；若某个状态 D 正在被祖先路径探索（尚未出栈），而兄弟分支抢先到达 D 时得到false，此时 D 自身的探索仍在进行——一旦 D 存在解，true会沿 D 自己的探索链向上传播，最终答案依然正确。换言之，这种标记方式等价于"每个状态只求值一次"，是标准记忆化搜索的变体写法。

四、测试验证：四个用例覆盖了哪些边界

测试文件 97. Interleaving String_test.go 采用仓库统一的question97/para97/ans97表驱动风格，内置四个用例：

前三个对应该题文档中的官方示例；第四个是仓库测试自行补充的，专门验证 3.1 节的长度前置剪枝。断言逻辑位于 Test_Problem97：调用isInterleave后将结果与期望值比对，不一致时以t.Fatalf输出输入、期望与实际值。

在仓库根目录执行以下命令即可单独验证本题：

go test -v ./leetcode/0097.Interleaving-String/

仓库还提供了 gotest.sh 脚本，对全部./leetcode/...包执行带覆盖率的测试（go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...），该脚本注释中特别说明：Go 1.10+ 支持对多个包一次性-coverprofile直接产出单个合法的覆盖率文件，避免旧写法"逐包生成再拼接"导致 Codecov 解析失败的问题。本题实现的每条分支（双匹配、单匹配、无匹配、越界保护）均可被上述四个用例驱动到，这也是仓库整体宣称"100% test coverage"的验证方式之一。

五、复杂度分析与 Follow up 的空间优化路径

结合状态空间分析可以得出该实现的确切复杂度：

• 时间：状态总数不超过(len(s1)+1) * (len(s2)+1)，即 O(m×n)（m、n 分别为s1、s2长度），每个状态做常数次字符比较与转移，总时间 O(m×n)。记忆化保证每个状态只求值一次，消除了朴素深搜的指数级重复交叉判断；
• 空间：visited最多记录 O(m×n) 个状态，加上递归栈深度最多 m+n，额外空间 O(m×n)。

对于题面Follow up提出的"只用O(s2.length)额外空间"的要求，从本实现的自顶向下状态图可以自然推导出标准答案：由于状态(i, j)只依赖(i+1, j)与(i, j+1)两个后继，把记忆化 DFS 改写成逐行填表的二维 DP（dp[i][j]表示s1从i起、s2从j起的后缀能否交错出s3对应后缀）后，第i行只需第i+1行，滚动一行即可压缩到 O(n) 空间。本仓库的实现选择的是自顶向下 + map 记忆化路线，与自底向上 DP 在状态转移上完全同构，两条路线可以相互印证：如果某状态在 DP 表里为true，则 DFS 中必存在一条经过该状态的可行路径。

六、小结与延伸阅读

本题在仓库中的完整资料链为：英文题解 0097.Interleaving-String.md、中文题解 README.md、Go 实现 97. Interleaving String.go 与测试 97. Interleaving String_test.go。核心要点回顾：

1. 交错匹配的本质是在(p1, p2)二维状态网格上寻找从左上角到右下角的转移路径，下一字符判断位置恒为s3[p1+p2]；
2. len(s1)+len(s2) != len(s3)是成本最低的前置剪枝；
3. 记忆化必须配合一维唯一编码p1*len(s3)+p2使用，其正确性依赖于p2 < len(s3)的行列展开性质；
4. 时间 O(m×n)、空间 O(m×n)，Follow up 的 O(n) 空间可通过"自顶向下状态图同构的滚动数组 DP"达成。

这套"状态网格 + 记忆化深搜 + 状态编码压缩"的范式，对仓库中同属字符串匹配类的其他题目（如编辑距离、最长公共子序列等动态规划题）同样适用，可直接作为同类问题的解题模板参考。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go