小工具知识网

当前位置: 首页 > 行业知识 > 力扣--动态规划97.交错字符串

行业知识

力扣--动态规划97.交错字符串

2026-11-18 20:41:14 来源:互联网转载

���路分析:

  1. 动态规划数组定义:

    • dp[i][j] 表示:使用字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符,能否构成字符串 s3 的前 i + j 个字符的交错组合。
  2. 初始化:

    • dp[0][0] 初始化为 1,表示空串是 s1 和 s2 的交错组成。
    • 初始化第一行和第一列,检查 s1 和 s2 的前缀是否与 s3 的对应前缀相等,若相等则标记为 1。
  3. 递推关系:

    • 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。
  4. 最终结果:

    • dp[len1][len2] 的值将告诉我们整个字符串 s3 是否可以由 s1 和 s2 交错组成。
  5. 返回结果:

    • 返回 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 

上一篇:小猪微信CMS全方位解析,功能、优势与不足一网打尽!

下一篇:揭秘不要组成之奥秘,深度解析字义和用法!