Interview Classic 150 Problem P97 Interleaving String

---

Timeline

Timeline

2025-12-16

init

Dynamic Programming

---

Problem:

P97 Interleaving String

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

Let $\texttt{dp[i][j]}$ denote $\texttt{s1[0..=i-1]}$ (where $1 \leq i \leq \texttt{s1.length()}$) and $\texttt{s2[0..=j-1]}$(where $1 \leq j \leq \texttt{s2.length()}$) can interleave to form $\texttt{s3[0..=i+j-1]}$。$dp[0][0]$ represents $\texttt{s1}$、$\texttt{s2}$ and $\texttt{s3}$ both are empty strings.

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

• Considering only s1, i.e.,s1[0..=i-1]whether it can interleave to forms3[0..i-1], obviously

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

• Similarly, considering only s2, we have:

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

• Considering both s1 and s2, we have:

$$\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] denotes that s1[0..=i-1] and s2[0..=j-1] can interleave to form s3[0..=i+j-1]
                // dp[0][0] represents the empty string

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