leetcode_day48
本文最后更新于 2024年7月9日 晚上
今日内容:
- 115. 不同的子序列 hard
- 583. 两个字符串的删除操作 medium
- 72. 编辑距离 medium
115. 不同的子序列
题目:
给你两个字符串 s
和 t
,统计并返回在
s
的 子序列 中 t
出现的个数,结果需要对 \(10^9 + 7\) 取模。
示例 1:
输入:
s
="rabbbit"
,t
="rabbit"
输出: 3
解释:
如下所示, 有 3 种可以从
s
中得到"rabbit"
的方案。 - rabbbit - rabbbit - rabbbit
思路:
明确dp数组含义:两个子序列,仍然按照之前的老办法,二维dp,大小比串长度多1,方便初始化,\(dp[i][j]\)含义为:在\(s[0:i-1]\)中,\(t[0:j-1]\)出现的个数。
建立状态转移方程:整体分为两种情况:
- \(s[i-1] ==
t[j-1]\):此时最新的s[i-1]和t[j-1]相同:
如果算上\(s[i-1]\),\(t\)就会被消耗一个,此时子序列个数就为\(dp[i-1][j-1]\),表示
s[0:i-1]中t[0:j-1]出现次数
但根据示例可看出:即使\(s[i-1]==t[j-1]\),\(s[i-1]\)也可以不用于匹配,这时子序列个数就为\(dp[i-1][j]\),表示
s[0:i-2]
中t[0:j-1]
出现次数
- \(s[i-1] ≠
t[j-1]\):此时最新的\(s[i-1]\)和\(t[j-1]\)不相同,意味着s中未出现新的t,所以只继承前面的结果\(dp[i-1][j]\),表示
s[0:i-2]
中t[0:j-1]
出现的次数
由此可构建出状态转移方程:
- \(s[i-1] ==
t[j-1]\):此时最新的s[i-1]和t[j-1]相同:
\[ dp[i][j]\ = \begin{cases} 1, & \text{$j=0,\ i>0$} \\ 0, & \text{$i=0,\ j>0$} \\ dp[i-1][j-1]+dp[i-1][j], & \text{$s[i-1]=t[j-1],\ i,\ j>0$} \\ dp[i-1][j], & \text{$s[i-1]=t[j-1],\ i,\ j>0$} \end{cases} \]
根据状态转移方程可知需由左上遍历到右下
代码
1 |
|
583. 两个字符串的删除操作
题目:
给定两个单词 word1
和 word2
,返回使得
word1
和 word2
相同所需的最小步数。
每步可以删除任意一个字符串中的一个字符。
示例 1:
- 输入:
word1
="sea"
,word2
="eat"
- 输出: 2
- 解释: 第一步将
"sea"
变为"ea"
,第二步将"eat "
变为"ea"
思路:
二维dp:
- 确定dp数组以及下标含义
\(dp[i][j]\)表示\(word1[0:i-1]\)和\(word2[0:j-1]\)达到相等需要的最小步数
- 确定递推公式
- \(word1[i-1] == word2[j-1]\)时,无需删除,直接继承之前状态
- \(word1[i-1] ≠ word2[j-1]\)时:
- 删\(word1[i-1]\),步数为\(dp[i-1][j]+1\)
- 删\(word2[j-1]\),步数为\(dp[i][j-1]+1\)
- 都删了,步数为\(dp[i-1][j-1]+2 = dp[i-1][j] + 1\),和前两种情况相同
状态转移方程为:
\[ dp[i][j]\ = \begin{cases} i, & \text{$i>0,j=0$} \\ j, & \text{$j>0,i=0$} \\ min(dp[i-1][j], dp[i][j-1])+1, & \text{$i,\ j>0,\ word_1[i]≠word_2[j]$} \\ dp[i-1][j-1], & \text{else} \end{cases} \]
代码
1 |
|
72. 编辑距离
题目:
给你两个单词 word1
和 word2
, 请返回将
word1
转换成 word2
所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
思路:
经过前几题,这题要理解到插入其实相当于删除,在一个串中插入,就相当于在另一个串中删除
- 确定dp数组以及下标含义
\(dp[i][j]\)表示\(word1[0:i-1]\)和\(word2[0:j-1]\)达到相等需要的最小操作数
- 确定递推公式
- \(word1[i-1] == word2[j-1]\)时,无需操作,直接继承之前状态
- \(word1[i-1] ≠ word2[j-1]\)时:
- 删\(word1[i-1]\),步数为\(dp[i-1][j]+1\)
- 删\(word2[j-1]\),步数为\(dp[i][j-1]+1\)
- 替换其中一个,步数为\(dp[i-1][j-1]+1\)
状态转移方程为:
\[ dp[i][j]\ = \begin{cases} i, & \text{$i>0,j=0$} \\ j, & \text{$j>0,i=0$} \\ min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1, & \text{$i,\ j>0,\ word_1[i]≠word_2[j]$} \\ dp[i-1][j-1], & \text{else} \end{cases} \]
代码
1 |
|