LeetCode 97: Interleaving String (2D Dynamic Programming)
LeetCode 97Dynamic ProgrammingStringToday we solve LeetCode 97 - Interleaving String.
Source: https://leetcode.com/problems/interleaving-string/
English
Problem Summary
Given strings s1, s2, and s3, determine whether s3 can be formed by interleaving s1 and s2 while preserving the relative order of characters in each source string.
Key Insight
This is a prefix-composition problem. Let dp[i][j] mean whether the first i chars of s1 and first j chars of s2 can form the first i+j chars of s3.
Brute Force and Limitations
A DFS that branches between taking from s1 or s2 works conceptually, but many states repeat (i, j), causing exponential time without memoization.
Optimal Algorithm Steps (2D DP)
1) If s1.length + s2.length != s3.length, return false immediately.
2) Initialize dp[0][0] = true.
3) Fill first row/column: only one source string contributes.
4) For each dp[i][j], check two transitions:
- from dp[i-1][j] if s1[i-1] == s3[i+j-1]
- from dp[i][j-1] if s2[j-1] == s3[i+j-1]
5) Answer is dp[m][n].
Complexity Analysis
Time: O(mn).
Space: O(mn), where m = len(s1), n = len(s2).
Common Pitfalls
- Forgetting the length pre-check and doing unnecessary DP.
- Using wrong index for s3 (must be i + j - 1).
- Missing first-row/first-column initialization, causing false negatives.
- Treating this as LCS-style matching; interleaving requires exact full coverage.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) return false;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i <= m; i++) {
dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
}
for (int j = 1; j <= n; j++) {
dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
char c = s3.charAt(i + j - 1);
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == c)
|| (dp[i][j - 1] && s2.charAt(j - 1) == c);
}
}
return dp[m][n];
}
}func isInterleave(s1 string, s2 string, s3 string) bool {
m, n := len(s1), len(s2)
if m+n != len(s3) {
return false
}
dp := make([][]bool, m+1)
for i := range dp {
dp[i] = make([]bool, n+1)
}
dp[0][0] = true
for i := 1; i <= m; i++ {
dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]
}
for j := 1; j <= n; j++ {
dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1]
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
c := s3[i+j-1]
dp[i][j] = (dp[i-1][j] && s1[i-1] == c) || (dp[i][j-1] && s2[j-1] == c)
}
}
return dp[m][n]
}class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if (m + n != (int)s3.size()) return false;
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int i = 1; i <= m; ++i) {
dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1];
}
for (int j = 1; j <= n; ++j) {
dp[0][j] = dp[0][j - 1] && s2[j - 1] == s3[j - 1];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
char c = s3[i + j - 1];
dp[i][j] = (dp[i - 1][j] && s1[i - 1] == c)
|| (dp[i][j - 1] && s2[j - 1] == c);
}
}
return dp[m][n];
}
};class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, m + 1):
dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
c = s3[i + j - 1]
dp[i][j] = (dp[i - 1][j] and s1[i - 1] == c) or (dp[i][j - 1] and s2[j - 1] == c)
return dp[m][n]var isInterleave = function(s1, s2, s3) {
const m = s1.length, n = s2.length;
if (m + n !== s3.length) return false;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
dp[0][0] = true;
for (let i = 1; i <= m; i++) {
dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
}
for (let j = 1; j <= n; j++) {
dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
const c = s3[i + j - 1];
dp[i][j] = (dp[i - 1][j] && s1[i - 1] === c) || (dp[i][j - 1] && s2[j - 1] === c);
}
}
return dp[m][n];
};中文
题目概述
给定字符串 s1、s2、s3，判断 s3 是否能由 s1 和 s2 交错组成，且必须保持 s1 与 s2 各自字符的相对顺序。
核心思路
这是典型前缀拼接 DP。定义 dp[i][j] 表示：s1 前 i 个字符与 s2 前 j 个字符，能否组成 s3 前 i+j 个字符。
基线解法与不足
纯 DFS 会在很多状态重复分支（同一个 (i, j)），复杂度指数级。用 DP 或记忆化可以把重复子问题压到 O(mn)。
最优算法步骤（2D DP）
1）先检查长度：若 len(s1)+len(s2) != len(s3)，直接 false。
2）初始化 dp[0][0] = true。
3）填第一行和第一列（只能来自单一字符串）。
4）对每个 dp[i][j] 做两种转移：
- 若 dp[i-1][j] 为真且 s1[i-1] == s3[i+j-1]
- 或 dp[i][j-1] 为真且 s2[j-1] == s3[i+j-1]
5）最终答案是 dp[m][n]。
复杂度分析
时间复杂度：O(mn)。
空间复杂度：O(mn)。
常见陷阱
- 忘记做长度预检，白白跑完整个 DP。
- s3 下标写错，必须是 i+j-1。
- 第一行/第一列初始化遗漏，导致本该为真的路径被错杀。
- 误当作 LCS 类型问题；本题要求完整覆盖且顺序严格保留。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) return false;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i <= m; i++) {
dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
}
for (int j = 1; j <= n; j++) {
dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
char c = s3.charAt(i + j - 1);
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == c)
|| (dp[i][j - 1] && s2.charAt(j - 1) == c);
}
}
return dp[m][n];
}
}func isInterleave(s1 string, s2 string, s3 string) bool {
m, n := len(s1), len(s2)
if m+n != len(s3) {
return false
}
dp := make([][]bool, m+1)
for i := range dp {
dp[i] = make([]bool, n+1)
}
dp[0][0] = true
for i := 1; i <= m; i++ {
dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]
}
for j := 1; j <= n; j++ {
dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1]
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
c := s3[i+j-1]
dp[i][j] = (dp[i-1][j] && s1[i-1] == c) || (dp[i][j-1] && s2[j-1] == c)
}
}
return dp[m][n]
}class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if (m + n != (int)s3.size()) return false;
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int i = 1; i <= m; ++i) {
dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1];
}
for (int j = 1; j <= n; ++j) {
dp[0][j] = dp[0][j - 1] && s2[j - 1] == s3[j - 1];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
char c = s3[i + j - 1];
dp[i][j] = (dp[i - 1][j] && s1[i - 1] == c)
|| (dp[i][j - 1] && s2[j - 1] == c);
}
}
return dp[m][n];
}
};class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, m + 1):
dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
c = s3[i + j - 1]
dp[i][j] = (dp[i - 1][j] and s1[i - 1] == c) or (dp[i][j - 1] and s2[j - 1] == c)
return dp[m][n]var isInterleave = function(s1, s2, s3) {
const m = s1.length, n = s2.length;
if (m + n !== s3.length) return false;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
dp[0][0] = true;
for (let i = 1; i <= m; i++) {
dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
}
for (let j = 1; j <= n; j++) {
dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
const c = s3[i + j - 1];
dp[i][j] = (dp[i - 1][j] && s1[i - 1] === c) || (dp[i][j - 1] && s2[j - 1] === c);
}
}
return dp[m][n];
};
Comments