97. 交错字符串

发表于 分类于 阅读次数： Waline： 本文字数： 889 阅读时长 ≈ 3 分钟

考点

  • LCS
  • 滚动数组

思路

一、问题回顾

给定三个字符串：

  • \(s_1\)
  • \(s_2\)
  • \(s_3\)

要求判断： 是否可以通过保持字符相对顺序不变，将 \(s_1\) 与 \(s_2\) 的字符交错排列，恰好构成 \(s_3\)。

二、核心观察与剪枝（本题最大坑点）

2.1 长度剪枝（必要条件）

交错的本质是：

  • 从 \(s_1\) 中取 \(n_1\) 个字符
  • 从 \(s_2\) 中取 \(n_2\) 个字符

因此最终字符串长度必须满足： \[ |s_3| = |s_1| + |s_2| \] 若不满足该条件，则不可能构成交错字符串，可以立即返回 false。

1
2
if (n1 + n2 != n3)
    return false;

这一剪枝不仅是优化，更是防止状态语义错误和越界访问的安全保障。

2.2 初始状态的严格语义（最容易出错的地方）

定义状态前，必须先明确状态语义。

三、状态定义

设： \[ f[i][j] \] 表示：

使用 \(s_1\) 的前 \(i\) 个字符 和 \(s_2\) 的前 \(j\) 个字符 是否可以构成 \(s_3\) 的前 \(i+j\) 个字符

3.1 初始状态：\(f[0][0]\)

  • \(s_1\) 取空前缀
  • \(s_2\) 取空前缀
  • 构成 \(s_3\) 的空前缀

这是一个永远成立的事实： \[ f[0][0] = \text{true} \]

❗ 该值与字符串是否为空 无关 ❗ 不应写任何条件判断 ❗ 一旦写复杂条件，DP 语义立即被破坏

3.2 第一列初始化（只使用 \(s_1\)）

当 \(j = 0\) 时，只能从 \(s_1\) 中取字符： \[ f[i][0] = f[i-1][0] \land (s_1[i-1] = s_3[i-1]) \] 含义是：

前 \(i-1\) 个字符已经能匹配， 且当前字符也相等，才能继续成立。

3.3 第一行初始化（只使用 \(s_2\)）

同理，当 \(i = 0\) 时： \[ f[0][j] = f[0][j-1] \land (s_2[j-1] = s_3[j-1]) \]

四、状态转移方程

当 \(i \ge 1\) 且 \(j \ge 1\) 时：

令： \[ k = i + j - 1 \] 则 \(s_3[k]\) 必须来自以下两种情况之一：

情况 1：最后一个字符来自 \(s_1\)

\[ s_1[i-1] = s_3[k] \quad \land \quad f[i-1][j] = \text{true} \]

情况 2：最后一个字符来自 \(s_2\)

\[ s_2[j-1] = s_3[k] \quad \land \quad f[i][j-1] = \text{true} \]

综合转移公式

\[ f[i][j] = \big( f[i-1][j] \land s_1[i-1]=s_3[k] \big) \;\lor\; \big( f[i][j-1] \land s_2[j-1]=s_3[k] \big) \]

五、最终答案

\[ \boxed{f[n_1][n_2]} \]

表示是否可以使用完整的 \(s_1\) 与 \(s_2\) 构成完整的 \(s_3\)。

六、时间与空间复杂度

  • 时间复杂度： \[ O(n_1 \times n_2) \]

  • 空间复杂度： \[ O(n_1 \times n_2) \]

（可进一步优化为一维 DP，但非本题重点）

七、参考实现（AC 代码）

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
class Solution {
public:
    static const int maxn = 105;
    bool isInterleave(string s1, string s2, string s3) {
        bool f[maxn][maxn];
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
        if (n1 + n2 != n3)
            return 0;
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 1; i <= n1 && i <= n3; ++i)
            f[i][0] = f[i - 1][0] && (s1[i - 1] == s3[i - 1]);
        for (int i = 1; i <= n2 && i <= n3; ++i)
            f[0][i] = f[0][i - 1] && (s2[i - 1] == s3[i - 1]);
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                int k = i + j - 1;
                if (s1[i - 1] == s3[k])
                    f[i][j] |= f[i - 1][j];
                if (s2[j - 1] == s3[k])
                    f[i][j] |= f[i][j - 1];
            }
        }
        return f[n1][n2];
    }
};

滚动数组版：

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
class Solution {
public:
    static const int maxn = 105;
    bool isInterleave(string s1, string s2, string s3) {
        bool f[maxn];
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
        if (n1 + n2 != n3)
            return 0;
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int i = 1; i <= n2 && i <= n3; ++i)
            f[i] = f[i - 1] && (s2[i - 1] == s3[i - 1]);
        for (int i = 1; i <= n1; ++i) {
            f[0] &= (s1[i - 1] == s3[i - 1]);
            for (int j = 1; j <= n2; ++j) {
                int k = i + j - 1;
                if (s1[i - 1] != s3[k])
                    f[j] = 0;
                if (s2[j - 1] == s3[k])
                    f[j] |= f[j - 1];
            }
        }
        return f[n2];
    }
};