LeetCode 97. 交错字符串

📌 题目描述

题目级别：中等

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
交错的定义是：将 s1 和 s2 分割成若干非空子字符串，使得这些子字符串在保持原顺序的情况下，交替拼接能形成 s3。

• 示例 1:
  输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
  输出：true
• 示例 2:
  输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
  输出：false
• 提示:
  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • 进阶：您能否仅使用 $O(s2.length)$ 额外的内存空间来解决它？

💡 破题思路：网格路径模型与动态规划

这道题可以想象成一个 $l_1\times l_2$ 的网格矩阵。从左上角 $(0,0)$ 出发，目标是走到右下角 $(l_1,l_2)$。

• 向下走一步，意味着从 s1 中拿走一个字符去匹配 s3。
• 向右走一步，意味着从 s2 中拿走一个字符去匹配 s3。

1. 状态定义
设 $dp[i][j]$ 表示：s1 的前 $i$ 个字符和 s2 的前 $j$ 个字符，能否成功交错拼出 s3 的前 $i+j$ 个字符。

2. 边界预判 (剪枝)
如果 s1 和 s2 的长度之和不等于 s3 的长度，连拼都拼不齐，直接一票否决 return false;。

3. 状态转移方程
到达网格 $(i,j)$ 有两条路：

• 从上方来：如果 s1 的前 $i-1$ 个字符和 s2 的前 $j$ 个字符能拼成 s3 的前 $i+j-1$ 个字符（即 $dp[i-1][j]$ 为真），且 s1 的第 $i$ 个字符恰好等于 s3 的第 $i+j$ 个字符。
• 从左方来：如果 s1 的前 $i$ 个字符和 s2 的前 $j-1$ 个字符能拼成（即 $dp[i][j-1]$ 为真），且 s2 的第 $j$ 个字符恰好等于 s3 的第 $i+j$ 个字符。
  两者只要有一个为真，当前状态就为真。

💻 C++ 代码实现 (作者二维 DP 版 + 语法避坑)

⚠️ 工程避坑提示：原作者代码中使用了 bool dp[l1 + 1][l2 + 1];。在严格的 C++ 标准中，数组长度不可为变量（VLA）。工业界应当使用 std::vector。

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int l1 = s1.size(), l2 = s2.size(), l3 = s3.size();

        // 长度防线：如果总长度不符，直接返回 false
        if (l1 + l2 != l3) return false;

        // 规范声明二维动态数组，初始化全为 false
        vector<vector<bool>> dp(l1 + 1, vector<bool>(l2 + 1, false));
        
        dp[0][0] = true; // 空串与空串交错必定能拼成空串

        // 初始化第一列（只用 s1 去匹配 s3）
        for (int i = 1; i <= l1; i ++ )
        {
            dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
        }
        
        // 初始化第一行（只用 s2 去匹配 s3）
        for (int i = 1; i <= l2; i ++ )
        {
            dp[0][i] = dp[0][i - 1] && (s2[i - 1] == s3[i - 1]);
        }

        // 核心网格状态转移
        for (int i = 1; i <= l1; i ++ )
            for (int j = 1; j <= l2; j ++ )
            {
                dp[i][j] = (dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1])) || 
                           (dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1])); 
            }

        return dp[l1][l2];
    }
};