时间轴

2025-12-16

init

题目：

P97 交错字符串

https://leetcode.cn/problems/interleaving-string/description/?envType=study-plan-v2&envId=top-interview-150

设$ \texttt{dp[i][j]}\ $表示 $ \texttt{s1[0..=i-1]}$（其中 $1 \leq i \leq \texttt{s1.length()}$）和 $\texttt{s2[0..=j-1]}$（其中 $1 \leq j \leq \texttt{s2.length()}$）能交错组成 $\texttt{s3[0..=i+j-1]}$。$dp[0][0]$ 表示 $\texttt{s1}$、$\texttt{s2}$ 和 $\texttt{s3}$ 均取空字符串。

$$
\texttt{ dp[0][0] = true} \
$$

  • 只考虑 s1, 即s1[0..=i-1]能否交错组成s3[0..i-1]，显然

$$
\texttt{dp[i][0] = dp[i-1][0] && (s3[i - 1] == s1[i- 1]);} \
$$

  • 同理，只考虑 s2 有：

$$
\texttt{dp[0][j] = dp[0][j-1] && (s3[j - 1] == s2[j- 1]);} \
$$

  • 同时考虑 s1 和 s2 有：

$$
\texttt{from_s1 = dp[i-1][j] && (s1[i-1] == s3[i+j-1]);} \
$$

$$
\texttt{from_s2 = dp[i][j-1] && (s2[j-1] == s3[i+j-1]);} \
$$

$$
\texttt{dp[i][j] = from_s1 || from_s2;} \
$$

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <vector>
#include <string>

using std::string;
using std::vector;

class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3)
        {
                int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
                int i, j;
                bool from_s1, from_s2;

                if (n1 + n2 != n3) {
                        return false;
                }
                vector<vector<bool> > dp(n1 + 1, vector<bool>(n2 + 1, false));
                // dp[i][j] 表示 s1[0..=i-1] 和s2[0..=j-1]可以交错组成s3[0..=i+j-1]
                // dp[0][0] 表示空字符串

                dp[0][0] = true;

                for (i = 1; i <= n1; i++) {
                        dp[i][0] = dp[i - 1][0] && (s3[i - 1] == s1[i - 1]);
                }

                for (j = 1; j <= n2; j++) {
                        dp[0][j] = dp[0][j - 1] && (s3[j - 1] == s2[j - 1]);
                }

                for (i = 1; i <= n1; i++) {
                        for (j = 1; j <= n2; j++) {
                                from_s1 = dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1]);
                                from_s2 = dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1]);
                                dp[i][j] = from_s1 || from_s2;
                        }
                }
                return dp[n1][n2];
        }
};