动态规划-leetcode#97-交错字符串

2024-05-30 04:58

本文主要是介绍动态规划-leetcode#97-交错字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {if(s1.length()+s2.length()!=s3.length()) return false;vector<vector<bool>> dp(s1.length()+1,vector<bool>(s2.length()+1,false));dp[0][0]=true;//s1空,s2空,可以组成s3空for(int i=0;i<=s1.length();i++){for(int j=0;j<=s2.length();j++){int id = i+j-1;if(i>=1 && s1[i-1]==s3[id] && dp[i-1][j]) dp[i][j]=true; if(j>=1 && s2[j-1]==s3[id]  && dp[i][j-1]) dp[i][j]=true; }}return dp[s1.length()][s2.length()];}
};

题意解析:s1和s2交错拼接,是否可以拼成s3,这里需要注意的是s1和s2必须是顺次访问的,不能跳着取字符去拼接,就是每次都要从剩余的字符串的头部还是取。举例aabcc和dbbca是否能拼成aadbbbaccc,dp[i][j] 表示s1的前i个与s2的前j个是否可以拼成s3的前i+j个,那么就有两种情况,要么最后一个字符来自s1,要么来自s2,如果s3的前i+j个字符的最后一个字符s3[i+j-1]来自s1,也就是s3[i+j-1]和s1[i-1]相等,那么只要dp[i-1][j]是true,dp[i][j]就是true;如果s3的前i+j个字符的最后一个字符s3[i+j-1]来自s2,也就是s3[i+j-1]和s2[j-1]相等,那么只要dp[i][j-1]是true,dp[i][j]就是true。

初始时候,s1=空串,s2=空串,组成的s3也是空串,dp[0][0]=true;这里的循环i和j表示的是前i个字符和前j个字符,当比较字符是否相等时,索引为i-1,j-1,i+j-1。

这篇关于动态规划-leetcode#97-交错字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1015631

相关文章

Java使用正则提取字符串中的内容的详细步骤

《Java使用正则提取字符串中的内容的详细步骤》:本文主要介绍Java中使用正则表达式提取字符串内容的方法,通过Pattern和Matcher类实现,涵盖编译正则、查找匹配、分组捕获、数字与邮箱提... 目录1. 基础流程2. 关键方法说明3. 常见场景示例场景1:提取所有数字场景2:提取邮箱地址4. 高级

Python 字符串裁切与提取全面且实用的解决方案

《Python字符串裁切与提取全面且实用的解决方案》本文梳理了Python字符串处理方法,涵盖基础切片、split/partition分割、正则匹配及结构化数据解析(如BeautifulSoup、j... 目录python 字符串裁切与提取的完整指南 基础切片方法1. 使用切片操作符[start:end]2

MyBatis的xml中字符串类型判空与非字符串类型判空处理方式(最新整理)

《MyBatis的xml中字符串类型判空与非字符串类型判空处理方式(最新整理)》本文给大家介绍MyBatis的xml中字符串类型判空与非字符串类型判空处理方式,本文给大家介绍的非常详细,对大家的学习或... 目录完整 Hutool 写法版本对比优化为什么status变成Long?为什么 price 没事?怎

浅谈MySQL的容量规划

《浅谈MySQL的容量规划》进行MySQL的容量规划是确保数据库能够在当前和未来的负载下顺利运行的重要步骤,容量规划包括评估当前资源使用情况、预测未来增长、调整配置和硬件资源等,感兴趣的可以了解一下... 目录一、评估当前资源使用情况1.1 磁盘空间使用1.2 内存使用1.3 CPU使用1.4 网络带宽二、

MySQL常用字符串函数示例和场景介绍

《MySQL常用字符串函数示例和场景介绍》MySQL提供了丰富的字符串函数帮助我们高效地对字符串进行处理、转换和分析,本文我将全面且深入地介绍MySQL常用的字符串函数,并结合具体示例和场景,帮你熟练... 目录一、字符串函数概述1.1 字符串函数的作用1.2 字符串函数分类二、字符串长度与统计函数2.1

C# $字符串插值的使用

《C#$字符串插值的使用》本文介绍了C#中的字符串插值功能,详细介绍了使用$符号的实现方式,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录$ 字符使用方式创建内插字符串包含不同的数据类型控制内插表达式的格式控制内插表达式的对齐方式内插表达式中使用转义序列内插表达式中使用

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发,所以面试百分百会问到

详解MySQL中JSON数据类型用法及与传统JSON字符串对比

《详解MySQL中JSON数据类型用法及与传统JSON字符串对比》MySQL从5.7版本开始引入了JSON数据类型,专门用于存储JSON格式的数据,本文将为大家简单介绍一下MySQL中JSON数据类型... 目录前言基本用法jsON数据类型 vs 传统JSON字符串1. 存储方式2. 查询方式对比3. 索引

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函