每日OJ题_两个数组dp⑥_力扣97. 交错字符串

2024-04-09 23:28

本文主要是介绍每日OJ题_两个数组dp⑥_力扣97. 交错字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

力扣97. 交错字符串

解析代码


力扣97. 交错字符串

97. 交错字符串

难度 中等

给定三个字符串 s1s2s3,请你帮忙验证 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 + t3 + s3 + ...

注意:a + b 意味着字符串 a 和 b 连接。

示例 1:

输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出:true

示例 2:

输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出:false

示例 3:

输入:s1 = "", s2 = "", s3 = ""
输出:true

提示:

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1s2、和 s3 都由小写英文字母组成

进阶:您能否仅使用 O(s2.length) 额外的内存空间来解决它?

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {}
};

解析代码

状态表示:对于两个字符串之间的 dp 问题,一般的思考方式如下:

        选取第一个字符串的 [0, i] 区间以及第二个字符串的 [0, j] 区间当成研究对象,结合题目的要求来定义状态表示。然后根据两个区间上最后一个位置的字符,来进行分类讨论,从而确定状态转移方程。

dp[i][j] 表示字符串 s1 中 [1, i] 区间内的字符串以及 s2 中 [1, j] 区间内的字符串,能否拼接成 s3 中 [1, i + j] 区间内的字符串。


状态转移方程:

        先分析一下题目,题目中交错后的字符串为 s1 + t1 + s2 + t2 + s3 + t3...... ,看似一个 s 一个 t 。实际上 s1 能够拆分成更小的一个字符,进而可以细化成 s1 + s2 +s3 + t1 + t2 + s4...... 。也就是说,并不是前一个用了 s 的子串,后一个必须要用 t 的子串。这对状态转移方程很重要。

继续根据两个区间上最后一个位置的字符,结合题目要求,来进行分类讨论:

  • 当 s3[i + j] = s1[i] 的时候,说明交错后的字符串的最后一个字符和 s1 的最后一个字符匹配了。那么整个字符串能否交错组成,变成:s1 中 [1, i - 1] 区间上的字符串以及 s2 中 [1, j] 区间上的字符串,能否交错形成 s3 中 [1, i + j - 1] 区间上的字符串,也就是 dp[i - 1][j] ; 此时 dp[i][j] = dp[i - 1][j] ;
  • 类似的,当 s3[i + j] = s2[j] 的时候,说明交错后的字符串的最后一个字符和 s2 的最后一个字符匹配了。那么整个字符串能否交错组成,变成:s1 中 [1, i] 区间上的字符串以及 s2 中 [1, j - 1] 区间上的字符串,能够交错形成 s3 中 [1, i + j - 1] 区间上的字符串,也就是 dp[i][j - 1] ; 此时 dp[i][j] = dp[i][j - 1] ;
  • 当两者的末尾都不等于 s3 最后一个位置的字符时,说明不可能是两者的交错字符串。 dp[i][j] = false;

上两种情况下,只要有一个情况下能够交错组成目标串,就可以返回 true 。因此可以定义状态转移为:dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]) ; 只要有一个成立,结果就是 true 。


初始化、填表顺序、返回值:

初始化:空串是有研究意义的,因此我们将原始 dp 表的规模多加上一行和一列,表示空串。由于 dp 数组的值设置为是否匹配,为了不与答案值混淆,我们需要将整个数组初始化为false 。由于需要用到前一行和前一列的状态,初始化第一行、第一列即可。

dp[0][0] = true ,因为空串 + 空串能够构成一个空串。

第一行表示 s1 是一个空串, 只用考虑 s2 即可。因此状态转移之和 s2 有关: dp[0][j] = s2[j - 1] == s3[j - 1] && dp[0][j - 1] , j 从 1 到 n ( n 为 s2 的长度),

第一列表示 s2 是一个空串, 只用考虑 s1 即可。因此状态转移之和 s1 有关: dp[i][0] = s1[i - 1] == s3[i - 1] && dp[i - 1][0] , i 从 1 到 m ( m 为 s1 的⻓度)

填表顺序:从上往下填写每一行,每一行从左往右,最后返回dp[m][n]。

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int m = s1.size(), n = s2.size();if(m + n != s3.size())return false;s1 = " " + s1, s2 = " " + s2, s3 = " " + s3;vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));// dp[i][j] 表⽰字符串s1中[1, i]区间内的字符串以及 // s2中[1, j]区间内的字符串,能否拼接成s3中[1, i + j]区间内的字符串dp[0][0] = true;for(int j = 1; j <= n; ++j) // 第一行,s1为空{if(s2[j] == s3[j])dp[0][j] = true;elsebreak;}for(int i = 1; i <= m; ++i) // 第一列,s2为空{if(s1[i] == s3[i])dp[i][0] = true;elsebreak;}for(int i = 1; i <= m; ++i){for(int j = 1; j <= n; ++j){dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j])|| (s2[j] == s3[i + j] && dp[i][j - 1]);// 也可以用下面注释// if(s1[i] == s3[i + j])// {//     dp[i][j] = dp[i - 1][j];//     if(dp[i][j] == true)//         continue;// }// if(s2[j] == s3[i + j])//     dp[i][j] = dp[i][j - 1];}}return dp[m][n];}
};

这篇关于每日OJ题_两个数组dp⑥_力扣97. 交错字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/889500

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]

uva 10118 dP

题意: 给4列篮子,每次从某一列开始无放回拿蜡烛放入篮子里,并且篮子最多只能放5支蜡烛,数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时,猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs

uva 10069 DP + 大数加法

代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl

uva 10029 HASH + DP

题意: 给一个字典,里面有好多单词。单词可以由增加、删除、变换,变成另一个单词,问能变换的最长单词长度。 解析: HASH+dp 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc