LeetCode 97. 交错字符串 - 二维DP经典题解（C语言实现）-程序员充电站

这道题是经典的二维 DP 题，非常适合用来练习“前缀 + 坐标路径”的思路。leetcode+1

题目与交错定义

给定三个字符串 s1、s2、s3，判断 s3 是否可以由 s1 和 s2 交错组成。leetcode

交错的含义是：保持 s1、s2 各自字符相对顺序不变，把它们按某种顺序“插”在一起，形成 s3。leetcode

例如：s1 = “aabcc”，s2 = “dbbca”，可以拆成 “aa” + “bc” + “c” 和 “dbbc” + “a”，交错后得到 “aadbbcbcac”，所以返回 true。leetcode

DP 状态设计：坐标视角

定义 dp[i][j]：是否可以用 s1 的前 i 个字符和 s2 的前 j 个字符，组成 s3 的前 i + j 个字符。leetcode

因为 i、j 都要包括“前 0 个字符”的情况，所以 i ∈ [0, m]，j ∈ [0, n]，需要开一个 (m+1) x (n+1) 的 dp 数组。leetcode+1

可以把 (i, j) 看成一张网格上的坐标：

向下走一步 (i-1, j) -> (i, j) 表示多用一个 s1 的字符。
向右走一步 (i, j-1) -> (i, j) 表示多用一个 s2 的字符。

这样，一条从 (0,0) 走到 (m,n) 的路径，就对应着一种“取字符顺序”的交错方式。

边界与初始化细节

长度剪枝非常重要：如果 len(s1) + len(s2) != len(s3)，直接返回 false，无需 DP。leetcode+1

dp[0][0] = true：用空串 s1 的前 0 个 + 空串 s2 的前 0 个，自然可以组成 s3 的前 0 个（空串）。leetcode+1

第一行 dp[0][j]：只使用 s2 的前 j 个字符，判断能否等于 s3 的前 j 个：

递推关系：dp[0][j] = dp[0][j-1] && (s2[j-1] == s3[j-1])。leetcode

第一列 dp[i][0]：只使用 s1 的前 i 个字符，判断能否等于 s3 的前 i 个：

递推关系：dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1])。leetcode

在代码中，这部分写成了边界分支：

dp[0][0]=true;for(i=0;i<=s1_len;i++){for(j=0;j<=s2_len;j++){if(i==0&&j==0)continue;elseif(i==0){if(s2[j-1]==s3[i+j-1])dp[i][j]=dp[i][j-1];}elseif(j==0){if(s1[i-1]==s3[i+j-1])dp[i][j]=dp[i-1][j];}...}}

可以看到，i == 0 的时候只从左边来，j == 0 的时候只从上边来，语义完全对应“只用一个字符串”的情况。leetcode

核心转移：如何体现“连续多字符交错”

很多人一开始会有疑惑：转移看起来只是在比较一个字符：

d p [ i ] [ j ] = ( d p [ i − 1 ] [ j ] ∧ s 1 [ i − 1 ] = = s 3 [ i + j − 1 ] ) ∨ ( d p [ i ] [ j − 1 ] ∧ s 2 [ j − 1 ] = = s 3 [ i + j − 1 ] ) dp[i][j] = (dp[i-1][j] \wedge s1[i-1] == s3[i+j-1]) \vee (dp[i][j-1] \wedge s2[j-1] == s3[i+j-1])dp[i][j]=(dp[i−1][j]∧s1[i−1]==s3[i+j−1])∨(dp[i][j−1]∧s2[j−1]==s3[i+j−1])

那像 “aa” + “dbbc” + “bc” 这种中间连续好几个字符来自同一个串的情况，怎么体现呢？

关键在于：

dp[i-1][j] 或 dp[i][j-1] 本身就已经包含了“一整段连续来自某个字符串”的历史信息。

例如连续从 s2 取 “dbbc”，在网格上就是从 (2,0) 走到 (2,4) 的四步右移，每一步都用：

dp[2][1] 依赖 dp[2][0]；
dp[2][2] 依赖 dp[2][1]；
dp[2][3] 依赖 dp[2][2]；
dp[2][4] 依赖 dp[2][3]。

每次只比较一个字符，但多次叠加，最终就形成“连续几个字符都从 s2 取”的效果。

代码对应实现：

else{if(s3[i+j-1]==s1[i-1]&&dp[i-1][j])dp[i][j]=true;elseif(s3[i+j-1]==s2[j-1]&&dp[i][j-1])dp[i][j]=true;elsedp[i][j]=false;}

这里：

从上方来：说明当前字符来自 s1，并且之前 (i-1, j) 这条路径是合法的交错。
从左边来：说明当前字符来自 s2，并且之前 (i, j-1) 这条路径是合法的交错。

任意一种成立，就能把一条合法路径扩展一位。

完整 C 代码与复杂度

完整通过 LeetCode 的 C 代码如下（二维 DP 版）：leetcode

#include<stdbool.h>#include<stdlib.h>#include<string.h>boolisInterleave(char*s1,char*s2,char*s3){ints1_len,s2_len,s3_len;bool**dp,result;inti,j;// 题目输入在 LeetCode 环境下不会是 NULL，这段可以有也可以去掉if(s1==NULL||s2==NULL||s3==NULL)returnfalse;s1_len=strlen(s1);s2_len=strlen(s2);s3_len=strlen(s3);// 长度剪枝if(s1_len+s2_len!=s3_len)returnfalse;// 分配 (m+1) x (n+1) 的 DP 数组dp=(bool**)malloc((s1_len+1)*sizeof(bool*));for(i=0;i<=s1_len;i++){dp[i]=(bool*)malloc((s2_len+1)*sizeof(bool));for(j=0;j<=s2_len;j++){dp[i][j]=false;}}dp[0][0]=true;for(i=0;i<=s1_len;i++){for(j=0;j<=s2_len;j++){if(i==0&&j==0)continue;elseif(i==0){if(s2[j-1]==s3[i+j-1])dp[i][j]=dp[i][j-1];}elseif(j==0){if(s1[i-1]==s3[i+j-1])dp[i][j]=dp[i-1][j];}else{if(s3[i+j-1]==s1[i-1]&&dp[i-1][j])dp[i][j]=true;elseif(s3[i+j-1]==s2[j-1]&&dp[i][j-1])dp[i][j]=true;elsedp[i][j]=false;}}}result=dp[s1_len][s2_len];for(i=0;i<=s1_len;i++){free(dp[i]);}free(dp);returnresult;}