【面试经典150 | 动态规划】交错字符串

这篇具有很好参考价值的文章主要介绍了【面试经典150 | 动态规划】交错字符串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【动态规划】【字符串】


题目来源

97. 交错字符串

【面试经典150 | 动态规划】交错字符串,面试经典150题,动态规划,字符串,C++

解题思路

方法一:动态规划

首先进行特判,记字符串 s1 的长度、字符串 s2 的长度、字符串 s3 的长度分别为 mnt。如果 m + n != t,那么 s3 一定无法由 s1s2 交错组成。

定义状态

m + n = t 时,定义 f[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 字符是否能交错组成 s3 的前 i+j 个字符。

转移关系

如果 s1 的第 i 个字符和 s3 的第 i+j 个字符相同,那么 s1 的前 i 个字符和 s2 的前 j 字符是否能交错组成 s3 的前 i+j 个字符 取决于 s1 的前 i-1 个字符和 s2 的前 j 字符是否能交错组成 s3 的前 i+j-1 个字符,即有:

KaTeX parse error: Expected 'EOF', got '&' at position 22: …j] = f[i-1][j] &̲ (s_1[i-1] == s…

同理,如果 s2 的第 j 个字符和 s3 的第 i+j 个字符相同,那么 s1 的前 i 个字符和 s2 的前 j 字符是否能交错组成 s3 的前 i+j 个字符 取决于 s1 的前 i 个字符和 s2 的前 j-1 字符是否能交错组成 s3 的前 i+j-1 个字符,即有:

KaTeX parse error: Expected 'EOF', got '&' at position 22: …j] = f[i][j-1] &̲ (s_2[j-1] == s…

base case

边界条件为 f[0][0] = true

最后返回

最终返回 f[m][n],表示字符串 s3 是否可以右字符串 s1s2 交错形成。

朴素实现代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size(), t = s3.size();
        if (m + n != t) return false;

        vector<vector<int>> f(m+1, vector<int>(n+1, false));

        f[0][0] = true; // base case 空字符串可以交错形成空字符串
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[i][j] |= f[i-1][j] && (s1[i-1] == s3[p]);
                }
                if (j > 0) {
                    f[i][j] |= f[i][j-1] && (s2[j-1] == s3[p]);
                }
            }
        }
        return f[m][n];
    }
};

使用滚动数组优化空间复杂度。 因为这里数组 f 的第 i 行只和第 i−1 行相关,所以我们可以用滚动数组优化这个动态规划,这样空间复杂度可以变成 O ( m ) O(m) O(m)

空间优化代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size(), t = s3.size();
        if (m + n != t) return false;

        vector<int> f(n+1, false);

        f[0] = true; // base case 空字符串可以交错形成空字符串
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[j] &= (s1[i-1] == s3[p]);
                }
                if (j > 0) {
                    f[j] |= f[j-1] && (s2[j-1] == s3[p]);
                }
            }
        }
        return f[n];
    }
};

复杂度分析

时间复杂度: O ( m n ) O(mn) O(mn) m m m 为字符串 s1 的长度, n n n 为字符串 s2 的长度。

空间复杂度:按行进行滚动数组优化后的空间复杂度为 O ( m ) O(m) O(m),朴素动态规划的时间复杂度为 O ( m n ) O(mn) O(mn)


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。文章来源地址https://www.toymoban.com/news/detail-852176.html

到了这里,关于【面试经典150 | 动态规划】交错字符串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode刷题之路】面试经典150题(8)——位运算+数学+一维动态规划+多维动态规划

    20 位运算 20.1 【位运算】二进制求和 题目地址:https://leetcode.cn/problems/add-binary/description/?envType=study-plan-v2envId=top-interview-150   按位逆序运算。 20.2 【位运算】颠倒二进制位 题目地址:https://leetcode.cn/problems/reverse-bits/description/?envType=study-plan-v2envId=top-interview-150   详见代码

    2024年04月16日
    浏览(73)
  • 力扣_字符串7—交错字符串

    给定三个字符串 s 1 、 s 2 、 s 3 s1、s2、s3 s 1 、 s 2 、 s 3 ,请你帮忙验证 s 3 s3 s 3 是否是由 s 1 s1 s 1 和 s 2 s2 s 2 交错 组成的。 两个字符串 s s s 和 t t t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s 1 + s 2 + . . . + s n s = s1 + s2 + ... + sn s = s 1

    2024年02月20日
    浏览(61)
  • 【经典面试】87 字符串解码

    给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string] ,表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。 此外,你

    2024年02月08日
    浏览(42)
  • 【动态规划】【字符串】扰乱字符串

    视频算法专题 动态规划汇总 字符串 使用下面描述的算法可以扰乱字符串 s 得到字符串 t : 如果字符串的长度为 1 ,算法停止 如果字符串的长度 1 ,执行下述步骤: 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串 s ,则可以将其分成两个子字符

    2024年02月03日
    浏览(58)
  • leetcode 97. 交错字符串

    给定三个字符串 s1、s2、s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。 两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s1 + s2 + … + sn t = t1 + t2 + … + tm |n - m| = 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t

    2024年02月09日
    浏览(38)
  • 小白水平理解面试经典题目LeetCode 594 最大和谐字符串

    这道题属于字符串类型题目,解决的办法还是有很多的,暴力算法,二分法,双指针等等。 和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。 现在,给你一个整数数组 nums ,请你在所有可能的子序列中找到最长的和谐子序列的长度。 数组的子序列是一个

    2024年01月23日
    浏览(47)
  • 【学会动态规划】环绕字符串中唯一的子字符串(25)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:467. 环绕字符串中唯一的子字

    2024年02月10日
    浏览(36)
  • 动态规划--通配字符串匹配

    1. 题目来源 链接:通配符匹配 来源:LeetCode 2. 题目说明 给定一个字符串 (s) 和一个字符模式 § ,实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。 ‘?’ 可以匹配任何单个字符。 ‘*’ 可以匹配任意字符串(包括空字符串)。 两个字符串完全匹配才算匹配成功。 说明: s 可能为

    2024年02月14日
    浏览(48)
  • 【动态规划】【字符串】132.分割回文串 II

    视频算法专题 动态规划汇总 字符串 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1: 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 示例 2: 输入:s = “a”

    2024年02月03日
    浏览(50)
  • 有效的括号字符串(力扣)动态规划、贪心 JAVA

    给你一个只包含三种字符的字符串,支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串,如果是有效字符串返回true 。 有效字符串符合如下规则: 任何左括号 ‘(’ 必须有相应的右括号 ‘)’。 任何右括号 ‘)’ 必须有相应的左括号 ‘(’

    2024年02月14日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包