【面试经典150 | 动态规划】交错字符串
文章目录
- 写在前面
- Tag
- 题目来源
- 解题思路
- 方法一:动态规划
- 写在最后
写在前面
本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……
专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:
- Tag:介绍本题牵涉到的知识点、数据结构;
- 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
- 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
- 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
- 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。
Tag
【动态规划】【字符串】
题目来源
97. 交错字符串
解题思路
方法一:动态规划
首先进行特判,记字符串 s1
的长度、字符串 s2
的长度、字符串 s3
的长度分别为 m
、n
和 t
。如果 m + n != t
,那么 s3
一定无法由 s1
和 s2
交错组成。
定义状态
在 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
是否可以右字符串 s1
和 s2
交错形成。
朴素实现代码
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)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。
相关文章:
【面试经典150 | 动态规划】交错字符串
文章目录 写在前面Tag题目来源解题思路方法一:动态规划 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行…...
设计模式(17):中介者模式
核心: 如果一个系统中对象之间的联系呈现网状结构,对象之间存在大量多对多关系,导致关系及其复杂,这些对象称为“同事对象”。我们可以引入一个中介者对象,使各个同事对象只跟中介者对象打交道,将复杂的网…...
echart 折线图或散点图当横坐标为小数位时,若想显示整数该如何处理?
如图当前是这样的: 横坐标刻度目前是小数位,如果直接将小数位取整则会失去精度,所以我们要做的是刻度即是整数,又能显示小数位对应的数值; 思路就是直接手动设置刻度:设置xAxis的min,max,splitNumber,同时不…...
一套C#自主版权+应用案例的手麻系统源码
手术麻醉信息管理系统源码,自主版权应用案例的手麻系统源码 手术麻醉信息管理系统包含了患者从预约申请手术到术前、术中、术后的流程控制。手术麻醉信息管理系统主要是由监护设备数据采集子系统和麻醉临床系统两个子部分组成。包括从手术申请到手术分配,…...
31.2k star, 免费开源的白板绘图工具 tldraw
31.2k star, 免费开源的白板绘图工具 tldraw 分类 开源分享 项目名: tldraw -- 无限画布白板 Github 开源地址: https://github.com/tldraw/tldraw 在线测试地址: tldraw 文档地址: tldraw SDK tldraw 是一款开源免费的无限画布白板&…...
Redis开源协议调整,我们怎么办?
2024年3月20日, Redis官方宣布,从 Redis 7.4版本开始,Redis将获得源可用许可证 ( RSALv2 ) 和服务器端公共许可证 ( SSPLv1 ) 的双重许可,时间点恰逢刚刚完成最新一轮融资,宣布的时机耐人寻味。 Redis协议调整,对云计算…...
干了三年外包。。。忘了什么是CICD。。。
干了三年外包。。。忘了什么是CICD。。。 CI/CD(持续集成与持续交付) 是一种软件开发实践,它可以帮助我们更快地交付高质量的软件产品。CI/CD的核心思想是将软件开发过程中的各个阶段自动化,从而减少人工干预,提高开发效率和产品质量。本文将…...
【LeetCode】454. 四数相加 II
目录 题目 思路 代码 题目 题目链接:. - 力扣(LeetCode) 给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足: 0 < i, j, k, l < nnums1…...
搜索(DFS BFS)
DFS 常规DFS: 二叉树前序,中序,后序遍历-CSDN博客 void postorderTraversal(root)初始化一个空列表 arrfind访问总树(root,arr)return arrvoid find(temp, arr)if temp 为空return // 调用顺序由前中后序决定find递归访问左子树find递归访问右子树arr加入当前节点…...
koc和kol是什么意思?
一、koc和kol是什么意思? koc和kol是专业术语。KOC是关键意见消费者的意思,是Key Opinion Consumer的缩写;KOL是关键意见领袖的意思,是Key Opinion Leader的缩写。 1、关键意见领袖kol “关键意见领袖”通俗地讲是达人。这些人…...
基于vscode Arduino插件开发Arduino项目
基于vscode Arduino插件开发arduino项目 插件配置问题记录1. 指定编译输出文件夹2. 编译下载时不输出详细信息3. 输出端口信息乱码4. 通过串口输出中文,vscode对应的串口助手上会显示乱码(未解决) 插件配置 环境:Arduino插件版本…...
AI 驱动强大是视频转换处理软件
由 AI 驱动的视频工具包。 增强、转换、录制和编辑视频AI 驱动的顶级视频工具包。 不论是老旧、低质、噪声或模糊的影片/图像,都能升级至 4K,稳定抖动的影片,提升帧率至 120/240fps,并能以全面 GPU 加速进行转换、压缩、录制和编辑…...
Python+requests+Pytest+logging+allure+pymysql框架详解
一、框架目录结构 1)tools目录用来放公共方法存储,如发送接口以及读取测试数据的方法,响应断言 数据库断言 前置sql等方法;2)datas目录用例存储接口用例的测试数据,我是用excel来存储的数据,文件数据 图片数据等;3)testcases目录用来存放测试用例,一个python文件对应…...
菜鸟笔记-Numpy函数-full/random.randint/random.choice
full函数 numpy.full 是 NumPy 库中的一个函数,它用于创建一个具有指定形状、数据类型和填充值的数组。此函数非常有用,因为它允许你快速生成一个具有相同值的数组,而无需手动设置每个元素。 1函数介绍 numpy.full(shape, fill_value, dty…...
蓝桥杯每日一题:牛的学术圈I(二分,双指针)
由于对计算机科学的热爱,以及有朝一日成为 「Bessie 博士」的诱惑,奶牛 Bessie 开始攻读计算机科学博士学位。 经过一段时间的学术研究,她已经发表了 N篇论文,并且她的第 i 篇论文得到了来自其他研究文献的 ci次引用。 Bessie 听…...
fping命令
fping是一个用于网络扫描的工具,它可以在 Linux 系统上使用。fping可以发送 ICMP ECHO_REQUEST(即 ping)数据包到指定的网络地址范围,并等待响应。通过这种方式,fping可以用来检测哪些 IP 地址是活跃的。 可以测试多个…...
奇富科技推出新一代全自研智能语音模型,打破沟通壁垒
“您好!请问是李先生噻?” 李先生刚接起电话,就被这熟悉的乡音逗乐了。这不是他所预料的常规客服,而是奇富科技新一代全自研智能语音模型——QI语精灵。这款模型不仅能用方言与人自然交流,还能在智能营销、贷后提醒、风…...
穿越代码之海:探寻结构体深层逻辑,展望未来应用新天地
欢迎来到白刘的领域 Miracle_86.-CSDN博客 系列专栏 C语言知识 先赞后看,已成习惯 创作不易,多多支持! 结构体作为一种数据结构,其定义和特点决定了它在各种应用中的广泛适用性。随着科技的进步和新兴行业的不断涌现…...
layui框架实战案例(26):layui-carousel轮播组件添加多个Echarts图标的效果
在Layui中,使用layui-carousel轮播组件嵌套Echarts图表来实现多个图表的展示。 css层叠样式表 调整轮播图背景色为白色;调整当个Echarts图表显示loading…状态;同一个DIV轮播项目添加多个Echarts的 .layui-carousel {background-color: #f…...
Unity开发一个FPS游戏之三
在前面的两篇博客中,我已实现了一个FPS游戏的大部分功能,包括了第一人称的主角运动控制,武器射击以及敌人的智能行为。这里我将继续完善这个游戏,包括以下几个方面: 增加一个真实的游戏场景,模拟一个废弃的…...
NIUSHOP完美运营版商城 虚拟商品全功能商城 全能商城小程序 智慧商城系统 全品类百货商城
完美运营版商城/拼团/团购/秒杀/积分/砍价/实物商品/虚拟商品等全功能商城 干干净净 没有一丝多余收据 还没过手其他站 还没乱七八走的广告和后门 后台可以自由拖曳修改前端UI页面 还支持虚拟商品自动发货等功能 挺不错的一套源码 前端UNIAPP 后端PHP 一键部署版本 源码免费…...
vue2开发好还是vue3开发好vue3.0开发路线
Vue 2和Vue 3都是流行的前端框架,它们各自有一些特点和优势。选择Vue 2还是Vue 3进行开发,主要取决于你的项目需求、团队的技术栈、以及对新特性的需求等因素。以下是一些关于Vue 2和Vue 3的比较,帮助你做出决策: Vue 2࿱…...
爬虫 新闻网站 并存储到CSV文件 以红网为例 V2.0 (控制台版)升级自定义查询关键词、时间段,详细注释
爬虫:红网网站, 获取指定关键词与指定时间范围内的新闻,并存储到CSV文件 V2.0(控制台版) 爬取目的:为了获取某一地区更全面的在红网已发布的宣传新闻稿,同时也让自己的工作更便捷 对比V1.0升级的…...
JavaSE-11笔记【多线程2(+2024新)】
文章目录 6.线程安全6.1 线程安全问题6.2 线程同步机制6.3 关于线程同步的面试题6.3.1 版本16.3.2 版本26.3.3 版本36.3.4 版本4 7.死锁7.1 多线程卖票问题 8.线程通信8.1 wait()和sleep的区别?8.2 两个线程交替输出8.3 三个线程交替输出8.4 线程通信-生产者和消费者…...
WebKit是什么?
WebKit是一个开源的浏览器引擎,它用于呈现网页内容在许多现代浏览器中,包括Safari浏览器、iOS内置浏览器、以及一些其他浏览器如Google Chrome的早期版本。以下是一些关于WebKit的重要信息: 起源和发展:WebKit最初是由苹果公司为其…...
谷歌(Google)历年编程真题——接雨水
谷歌历年面试真题——数组和字符串系列真题练习。 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:…...
golang 归并回源策略
前言 下面是我根据业务需求画了一个架构图,没有特别之处,很普通,都是我们常见的中间件,都是一些幂等性GET 请求。有一个地方很有意思,从service 分别有10000 qps 请求到Redis,并且它们的key 是一样的。这样…...
【漏洞复现】可视化融合指挥调度平台 dispatch接口处存在任意文件上传漏洞
免责声明:文章来源互联网收集整理,请勿利用文章内的相关技术从事非法测试,由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失,均由使用者本人负责,所产生的一切不良后果与文章作者无关。该…...
最讨厌这种字符串问题了!!
题目:洛谷P1957口算练习题 题目大意描述: 第一行输入一个整数表示接下来要进行多少次运算,接下来每行输入一个字母c和两个数字x,y(输入的字母为a/b/c,分别表示要进行,-,*运算)或者就输入两个数…...
B-名牌赌王(本人遇到的题,做个笔记)
题解: #include <iostream> #include <queue> //需要用小根堆的优先队列 #include <unordered_map> //用无序映射 using namespace std; bool pai() {int n, m;cin >> n >> m; priority_queue<int, vector<int>, gr…...
用asp.net做的网站框架/国内网络销售平台有哪些
斐波那契数列计算 B 描述 斐波那契数列如下: F(0) = 0, F(1) = 1 F(n) = F(n-1) + F(n-2) 编写一个计算斐波那契数列的函数,采用递归方式,输出不超过n的所有斐波那契数列元素 调用上述函数,完成如下功能: 用户输入一个整数n,输出所有不超过n的斐波那契数列元素、输出数列…...
企业门户网站建设公司/公司品牌宣传方案
silverlight中的IsolatedStorageSettings是一个独立存储空间,可以通过它来实现数据的存储于交互,如实现页面传值。使用前要先引入命名空间:using System.IO.IsolatedStorage; /// <summary> /// 声明独立存储 /// </s…...
网站建设一般好久到期/seo网站优化培训要多少钱
本教程用途:有IPV4公网IP的企业需要把内网网站,CRM,ERP等服务器能在公网访问。那么什么是端口映射(Port-Forwarding),那么就是要了解一下NAT和NAPT。NAT是网络地址转换。NAPT是网络地址端口转换。NAT是用于…...
做淘宝客导购网站/冯宗耀seo教程
《《JavaOOP项目案例》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《JavaOOP项目案例》PPT课件.ppt(10页珍藏版)》请在装配图网上搜索。1、学员成绩管理系统 Java高级编程 项目案例 项目目标 完成学生管理系统 项目需求 某班级的成绩管理系统&#x…...
购物帮做特惠的导购网站/北京seo网络优化招聘网
在edge浏览器下载tampermonkey 然后 这个网站 安装出来 再下载 https://www.lanzoui.com/b0ev69v1i 中文免激活绿色版(是一个IDM下载器) 下载完成后运行绿化.bat 把要下载的东西搞个分享链接 复制链接在edge浏览器打开 点击网盘工具箱直链 配置卡密 如果出现查询失败 就是需要…...
热门的网站模板下载/百度识图在线识别
收获最重要前言优化代码收获1.禁止浏览器弹窗2.定时器3.设置属性-隐藏元素4.鼠标悬停和移开事件5.添加元素6.div里均匀分布7.获取元素属性值8.监听播放器状态9.jQuery 选择器前言 有钱的可以支持一下原作者,没钱就要多学习 优化 1.1 视频刚开始未播放时ÿ…...