行业知识
力扣--动态规划97.交错字符串
2026-11-18 20:41:14
来源:互联网转载
���路分析:
-
动态规划数组定义:
- dp[i][j] 表示:使用字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符,能否构成字符串 s3 的前 i + j 个字符的交错组合。
-
初始化:
- dp[0][0] 初始化为 1,表示空串是 s1 和 s2 的交错组成。
- 初始化第一行和第一列,检查 s1 和 s2 的前缀是否与 s3 的对应前缀相等,若相等则标记为 1。
-
递推关系:
- dp[i][j] 的值取决于 s1[i-1]、s2[j-1] 与 s3[i+j-1] 是否匹配,以及之前的状态:
- 如果 s3[i+j-1] == s1[i-1] 且 dp[i-1][j] == 1,表示当前字符匹配且前缀也能交错组成,标记 dp[i][j] = 1。
- 如果 s3[i+j-1] == s2[j-1] 且 dp[i][j-1] == 1,表示当前字符匹配且前缀也能交错组成,标记 dp[i][j] = 1。
- dp[i][j] 的值取决于 s1[i-1]、s2[j-1] 与 s3[i+j-1] 是否匹配,以及之前的状态:
-
最终结果:
- dp[len1][len2] 的值将告诉我们整个字符串 s3 是否可以由 s1 和 s2 交错组成。
-
返回结果:
- 返回 dp[len1][len2]。
class Solution {public: // 判断字符串 s3 是否是由字符串 s1 和 s2 交错组成的 bool isInterleave(string s1, string s2, string s3) { // 获取字符串 s1、s2、s3 的长度 int len1 = s1.length(); int len2 = s2.length(); int len3 = s3.length(); // 如果 s1 和 s2 的长度之和不等于 s3 的长度,直接返回 false if (len1 + len2 != len3) return false; // 处理特殊情况:当 s1 为空时,判断 s2 和 s3 是否相等;当 s2 为空时,判断 s1 和 s3 是否相等 if (len1 == 0 && s2 == s3) return true; if (len2 == 0 && s1 == s3) return true; // 创建二维数组 dp,用于记录 s1 和 s2 是否能够交错组成 s3 的子串 vector dp(len1 + 1, vector(len2 + 1, 0)); // 初始化 dp[0][0] 为 1,表示空串是 s1 和 s2 的交错组成 dp[0][0] = 1; // 初始化第一行,如果 s1 的前缀和 s3 相等,标记 dp[i][0] 为 1 for (int i = 1; i