面试经典150题 P97 交错字符串

---

时间轴

时间轴

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;} \\$$

#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];
        }
};