多语言详解从「暴搜」到「记忆化搜索」再到「线性 DP（及其进阶）」
题目描述
这是 LeetCode 上的 97. 交错字符串 ，难度为 中等。
Tag : 「线性 DP」、「记忆化搜索」
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1
交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
注意：a + b 意味着字符串 a 和 b 连接。
示例 1：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true
示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false
示例 3：
输入：s1 = "", s2 = "", s3 = ""
输出：true
提示：
- 0<=s1.length,s2.length<=1000 <= s1.length, s2.length <= 1000<=s1.length,s2.length<=100
- 0<=s3.length<=2000 <= s3.length <= 2000<=s3.length<=200
s1、s2、和s3都由小写英文字母组成
进阶：您能否仅使用 O(s2.length)O(s2.length)O(s2.length) 额外的内存空间来解决它?
记忆化搜索
数据范围相比于「暴搜」而言有点大，但将「暴搜」解法作为前置思考，总能为我们带来灵感。
将 s1、s2 和 s3 的长度分别记为 nnn、mmm 和 lll。
一个显然的情况是若 n+mn + mn+m 不为 lll，必然不能用 s1 和 s2 来凑成 s3，返回 false。
定义暴搜函数为 boolean dfs(int i, int j)，代表当前处理到 s1 的第 iii 个字符，s2 的第 jjj 个字符，能否凑成 s3 的前 i+ji + ji+j 个字符。
最终答案为 dfs(0, 0)。
根据 s1[i]s1[i]s1[i]、s2[j]s2[j]s2[j] 和 s3[i+j]s3[i + j]s3[i+j] 的关系分情况讨论：
- s1[i]=s3[i+j]s1[i] = s3[i + j]s1[i]=s3[i+j]，可使用 s1[i]s1[i]s1[i] 充当 s3[i+j]s3[i + j]s3[i+j] ，暴搜 s1[i]s1[i]s1[i] 已被使用的情况，决策下一位
dfs(i + 1, j) - s2[j]=s3[i+j]s2[j] = s3[i + j]s2[j]=s3[i+j]，可使用 s2[j]s2[j]s2[j] 充当 s3[i+j]s3[i + j]s3[i+j] ，暴搜 s2[j]s2[j]s2[j] 已被使用的情况，决策下一位
dfs(i, j + 1)
当 i+j=li + j = li+j=l 时，代表我们成功用 s1 和 s2 凑成了 s3，返回 true；而若在任一回合出现 s1[i]≠s3[i+j]s1[i] \neq s3[i + j]s1[i]=s3[i+j] 且 s2[j]≠s3[i+j]s2[j] \neq s3[i + j]s2[j]=s3[i+j]，说明构造无法进行，返回 false。
TLE Java 代码：
class Solution {
char[] cs1, cs2, cs3;
int n, m, l;
public boolean isInterleave(String s1, String s2, String s3) {
cs1 = s1.toCharArray(); cs2 = s2.toCharArray(); cs3 = s3.toCharArray();
n = s1.length(); m = s2.length(); l = s3.length();
if (n + m != l) return false;
return dfs(0, 0);
}
boolean dfs(int i, int j) {
if (i + j == l) return true;
boolean ans = false;
if (i < n && cs1[i] == cs3[i + j]) ans |= dfs(i + 1, j);
if (j < m && cs2[j] == cs3[i + j]) ans |= dfs(i, j + 1);
return ans;
}
}
可分析上述 TLE 做法的时间复杂度上界为交错序列个数。
长度分别为 nnn 和 mmm 形成的交错序列数量为 C(n+m,n)=(n+m)!n!×m!C(n+m, n) = \frac{(n+m)!}{n! \times m!}C(n+m,n)=n!×m!(n+m)! : 从 n+mn + mn+m 个位置中选 nnn 个位置按顺序放置 s1，剩下的 mmm 个位置唯一确定的放置 s2。
实际上，不同交错序列之间有着相同的前缀（例如 s1 = aac 和 s2 = bbd，具体交错方案中的 aabbcd 和 aabbdc 之间有着相同的前缀 aabb__），可通过「记忆化搜索」来进行减少这些重复的构造。
直接根据 dfs 函数的入参构建缓存器 cache，起始 cache[i][j] = 0；若 cache[i][j] = 1 代表 true；cache[i][j] = -1 代表 false。
如此简单的改动，即可将朴素的 DFS 改成记忆化搜索。
Java 代码：
class Solution {
char[] cs1, cs2, cs3;
int n, m, l;
int[][] cache;
public boolean isInterleave(String s1, String s2, String s3) {
cs1 = s1.toCharArray(); cs2 = s2.toCharArray(); cs3 = s3.toCharArray();
n = s1.length(); m = s2.length(); l = s3.length();
if (n + m != l) return false;
cache = new int[n + 10][m + 10];
return dfs(0, 0);
}
boolean dfs(int i, int j) {
if (cache[i][j] != 0) return cache[i][j] == 1;
if (i + j == l) return true;
boolean ans = false;
if (i < n && cs1[i] == cs3[i + j]) ans |= dfs(i + 1, j);
if (j < m && cs2[j] == cs3[i + j]) ans |= dfs(i, j + 1);
cache[i][j] = ans ? 1 : -1;
return ans;
}
}
C++ 代码：
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n = s1.length(), m = s2.length(), l = s3.length();
if (n + m != l) return false;
vector<vector<int>> cache(n + 10, vector<int>(m + 10, 0));
function<bool(int, int)> dfs = [&](int i, int j) {
if (cache[i][j] != 0) return cache[i][j] == 1;
if (i + j == l) return true;
bool ans = false;
if (i < n && s1[i] == s3[i + j]) ans |= dfs(i + 1, j);
if (j < m && s2[j] == s3[i + j]) ans |= dfs(i, j + 1);
cache[i][j] = ans ? 1 : -1;
return ans;
};
return dfs(0, 0);
}
};
Python 代码：
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
n, m, l = len(s1), len(s2), len(s3)
if n + m != l:
return False
@lru_cache
def dfs(i, j):
if i + j == l:
return True
ans = False
if i < n and s1[i] == s3[i + j]:
ans |= dfs(i + 1, j)
if j < m and s2[j] == s3[i + j]:
ans |= dfs(i, j + 1)
return ans
return dfs(0, 0)
TypeScript 代码：
function isInterleave(s1: string, s2: string, s3: string): boolean {
const n = s1.length, m = s2.length, l = s3.length;
if (n + m !== l) return false;
const cache = new Array(n + 10).fill(0).map(() => new Array(m + 10).fill(0));
const dfs = (i: number, j: number): boolean => {
if (cache[i][j] !== 0) return cache[i][j] === 1;
if (i + j === l) return true;
let ans = false;
if (i < n && s1[i] === s3[i + j]) ans ||= dfs(i + 1, j);
if (j < m && s2[j] === s3[i + j]) ans ||= dfs(i, j + 1);
cache[i][j] = ans ? 1 : -1;
return ans;
};
return dfs(0, 0);
};
- 时间复杂度：共有 n×mn \times mn×m 个状态，复杂度为 O(n×m)O(n \times m)O(n×m)
- 空间复杂度：O(n×m)O(n \times m)O(n×m)
线性 DP
直接将「记忆化搜索」中的缓存器修改为我们的动态规划状态定义。
定义 f[i][j]f[i][j]f[i][j] 为使用 s1 的前 iii 个字符，使用 s2 的前 jjj 个字符，能否凑出 s3 的前 i+ji + ji+j 个字符。
为了方便，我们令所有字符串的下标均从 111 开始。
不失一般性，考虑 f[i][j]f[i][j]f[i][j] 如何转移，根据 s1[i]s1[i]s1[i]、s2[j]s2[j]s2[j] 和 s3[i+j]s3[i+j]s3[i+j] 是否相等进行分析，即根据当前 s3 的最后一个字符 s3[i+j]s3[i + j]s3[i+j] 由 s1[i]s1[i]s1[i] 和 s2[j]s2[j]s2[j] 谁来提供进行讨论：
- s1[i]=s3[i+j]s1[i] = s3[i + j]s1[i]=s3[i+j]：说明当前
s3的最后一个字符 s3[i+j]s3[i + j]s3[i+j] 可由 s1[i]s1[i]s1[i] 提供，而s3此前的 i+j−1i + j - 1i+j−1 个字符，可由s1的前 i−1i - 1i−1 字符和s2的前 jjj 个字符共同提供。此时若 f[i−1][j]f[i - 1][j]f[i−1][j] 为真，则有 f[i][j]f[i][j]f[i][j] 为真。 - s2[j]=s3[i+j]s2[j] = s3[i+j]s2[j]=s3[i+j]：说明当前
s3的最后一个字符串 s3[i+j]s3[i+j]s3[i+j] 可由 s2[j]s2[j]s2[j] 提供，而s3此前的 i+j−1i + j - 1i+j−1 个字符，可由s1的前 iii 字符和s2的前 j−1j - 1j−1 个字符共同提供。此时若 f[i][j−1]f[i][j - 1]f[i][j−1] 为真，则有 f[i][j]f[i][j]f[i][j] 为真。
综上，只有上述条件任一成立，f[i][j]f[i][j]f[i][j] 即为真。
一些细节：为了在转移过程中减少边界处理，我们先预处理出 f[0][X]f[0][X]f[0][X] 和 f[X][0]f[X][0]f[X][0] 的状态值（即 s1、s2 和 s3 之间的公共前缀）。
Java 代码：
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(), cs3 = s3.toCharArray();
int n = s1.length(), m = s2.length(), l = s3.length();
if (n + m != l) return false;
boolean[][] f = new boolean[n + 10][m + 10];
f[0][0] = true;
for (int i = 1; i <= n && f[i - 1][0]; i++) f[i][0] = cs1[i - 1] == cs3[i - 1];
for (int i = 1; i <= m && f[0][i - 1]; i++) f[0][i] = cs2[i - 1] == cs3[i - 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (cs1[i - 1] == cs3[i + j - 1]) f[i][j] |= f[i - 1][j];
if (cs2[j - 1] == cs3[i + j - 1]) f[i][j] |= f[i][j - 1];
}
}
return f[n][m];
}
}
Python 代码：
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
n, m, l = len(s1), len(s2), len(s3)
if n + m != l:
return False
f = [[False] * (m + 10) for _ in range(n + 10)]
f[0][0] = True
for i in range(1, n + 1):
f[i][0] = f[i - 1][0] and s1[i - 1] == s3[i - 1]
for i in range(1, m + 1):
f[0][i] = f[0][i - 1] and s2[i - 1] == s3[i - 1]
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i - 1] == s3[i + j - 1]:
f[i][j] |= f[i - 1][j]
if s2[j - 1] == s3[i + j - 1]:
f[i][j] |= f[i][j - 1]
return f[n][m]
C++ 代码：
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n = s1.length(), m = s2.length(), l = s3.length();
if (n + m != l) return false;
vector<vector<bool>> f(n + 10, vector<bool>(m + 10, false));
f[0][0] = true;
for (int i = 1; i <= n && f[i - 1][0]; i++) f[i][0] = (s1[i - 1] == s3[i - 1]);
for (int i = 1; i <= m && f[0][i - 1]; i++) f[0][i] = (s2[i - 1] == s3[i - 1]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i - 1] == s3[i + j - 1]) f[i][j] = f[i][j] | f[i - 1][j];
if (s2[j - 1] == s3[i + j - 1]) f[i][j] = f[i][j] | f[i][j - 1];
}
}
return f[n][m];
}
};
TypeScript 代码：
function isInterleave(s1: string, s2: string, s3: string): boolean {
const n = s1.length, m = s2.length, l = s3.length;
if (n + m !== l) return false;
const f = new Array(n + 10).fill(false).map(() => new Array(m + 10).fill(false));
f[0][0] = true;
for (let i = 1; i <= n && f[i - 1][0]; i++) f[i][0] = s1[i - 1] === s3[i - 1];
for (let i = 1; i <= m && f[0][i - 1]; i++) f[0][i] = s2[i - 1] === s3[i - 1];
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
if (s1[i - 1] === s3[i + j - 1]) f[i][j] ||= f[i - 1][j];
if (s2[j - 1] === s3[i + j - 1]) f[i][j] ||= f[i][j - 1];
}
}
return f[n][m];
};
- 时间复杂度：O(n×m)O(n \times m)O(n×m)
- 空间复杂度：O(n×m)O(n \times m)O(n×m)
进阶
根据状态转移方程可知 f[i][j]f[i][j]f[i][j] 仅依赖于 f[i−1][j]f[i - 1][j]f[i−1][j] 和 f[i][j−1]f[i][j - 1]f[i][j−1]，因此可通过「滚动数组」的方式进行优化。
状态定义不变，将动规数组开成 f[2][m+10]f[2][m + 10]f[2][m+10] 大小（另外一维的 +10 操作仅为个人习惯）。
随后，当我们需要更新 f[i][X] 时，需要写成 f[i & 1][X]；需要访问 f[i - 1][X] 时，则写成 f[(i - 1) & 1][X] 即可。
最后，同样是为了转移过程中减少边界处理，我们需要使用两个变量 a 和 b 记住 s1 和 s2 与 s3 的公共前缀，并特判掉 s1 或 s2 为空的情况。
Java 代码：
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(), cs3 = s3.toCharArray();
int n = s1.length(), m = s2.length(), l = s3.length();
if (n + m != l) return false;
int a = 0, b = 0;
while (a < n && cs1[a] == cs3[a]) a++;
while (b < m && cs2[b] == cs3[b]) b++;
if (m == 0) return n <= a;
if (n == 0) return m <= b;
boolean[][] f = new boolean[2][m + 10];
f[0][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
boolean cur = false;
if (cs1[i - 1] == cs3[i + j - 1]) {
if (i == 1) cur |= j <= b;
else cur |= f[(i - 1) & 1][j];
}
if (cs2[j - 1] == cs3[i + j - 1]) {
if (j == 1) cur |= i <= a;
else cur |= f[i & 1][j - 1];
}
f[i & 1][j] = cur;
}
}
return f[n & 1][m];
}
}
C++ 代码：
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n = s1.length(), m = s2.length(), l = s3.length();
if (n + m != l) return false;
int a = 0, b = 0;
while (a < n && s1[a] == s3[a]) a++;
while (b < m && s2[b] == s3[b]) b++;
if (n == 0) return m <= b;
if (m == 0) return n <= a;
vector<vector<bool>> f(2, vector<bool>(m + 1, false));
f[0][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
bool cur = false;
if (s1[i - 1] == s3[i + j - 1]) {
if (i == 1) cur |= j <= b;
else cur |= f[(i - 1) & 1][j];
}
if (s2[j - 1] == s3[i + j - 1]) {
if (j == 1) cur |= i <= a;
else cur |= f[i & 1][j - 1];
}
f[i & 1][j] = cur;
}
}
return f[n & 1][m];
}
};
Python 代码：
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
n, m, l = len(s1), len(s2), len(s3)
if n + m != l:
return False
a, b = 0, 0
while a < n and s1[a] == s3[a]:
a += 1
while b < m and s2[b] == s3[b]:
b += 1
if m == 0:
return n <= a
if n == 0:
return m <= b
f = [[False for _ in range(m + 1)] for _ in range(2)]
f[0][0] = True
for i in range(1, n+1):
for j in range(1, m+1):
cur = False
if s1[i - 1] == s3[i + j - 1]:
if i == 1:
cur |= j <= b
else:
cur |= f[(i - 1) & 1][j]
if s2[j - 1] == s3[i + j - 1]:
if j == 1:
cur |= i <= a
else:
cur |= f[i & 1][j - 1]
f[i & 1][j] = cur
return f[n & 1][m]
TypeScript 代码：
function isInterleave(s1: string, s2: string, s3: string): boolean {
const n = s1.length, m = s2.length, l = s3.length;
if (n + m !== l) return false;
let a = 0, b = 0;
while (a < n && s1[a] === s3[a]) a++;
while (b < m && s2[b] === s3[b]) b++;
if (m == 0) return n <= a;
if (n == 0) return m <= b;
const f = new Array(2).fill(null).map(() => new Array(m + 1).fill(false));
f[0][0] = true;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
let cur = false;
if (s1[i - 1] === s3[i + j - 1]) {
if (i === 1) cur ||= j <= b;
else cur ||= f[(i - 1) & 1][j];
}
if (s2[j - 1] === s3[i + j - 1]) {
if (j === 1) cur ||= i <= a;
else cur ||= f[i & 1][j - 1];
}
f[i & 1][j] = cur;
}
}
return f[n & 1][m];
};
- 时间复杂度：O(n×m)O(n \times m)O(n×m)
- 空间复杂度：O(m)O(m)O(m)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.97 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉