72. 编辑距离
题目描述
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
思路分析
动规五部曲
- 确定dp数组以及下标的含义
dp[i] [j]表示以i-1结尾的字符串word1和以下标j-1结尾的字符串word2,最近编辑距离为dp[i] [j]
- 确定递推公式
考虑下编辑的几种操作,整理如下:
if (word1[i - 1] == word2[j - 1]) 不操作 if (word1[i - 1] != word2[j - 1]) 增 删 换
word1[i - 1] == word2[j - 1] ,则不用任何编辑,就和之前一样了. 即 dp[i][j] = dp[i - 1][j - 1];
word1[i - 1] != word2[j - 1] 那么就需要编辑了.
操作一: word1删除一个元素. 那么就是以下标i-2结尾的word1与j-1结尾的word2的最近编辑距离 再加上一个操作. 即 dp[i][j] = dp[i-1][j] + 1
操作二:word2删除一个元素.那么就是以下标i-1结尾的word1与j-2结尾的word2的最近编辑距离 再加上一个操作. 即 dp[i][j] = dp[i][j - 1] + 1;
操作三:替换元素. word1替换word1[i-1],使其与word2[j-1]相同,此时不用增加元素,那么以下标 i-2结尾的word1与j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作. 即 dp[i][j] = dp[i - 1][j - 1] + 1;
这里有同学发现了，怎么都是删除元素，添加元素去哪了。
word2添加一个元素，相当于word1删除一个元素，例如 word1 = "ad" ，word2 = "a"，word1删除元素'd' 和 word2添加一个元素'd'，变成word1="a", word2="ad"， 最终的操作数是一样！
dp数组如何初始化
dp[i] [0] ：以下标i-1为结尾的字符串word1，和空字符串word2，那么最近编辑距离dp[i] [0]=i。同理 dp[0] [j] = j;
确定遍历顺序
从如下四个递推公式：
dp[i][j] = dp[i - 1][j - 1]
dp[i][j] = dp[i - 1][j - 1] + 1
dp[i][j] = dp[i][j - 1] + 1
dp[i][j] = dp[i - 1][j] + 1
可以看出dp[i] [j]是依赖左方，上方和左上方元素的，如图：
所以在dp矩阵中一定是从左到右从上到下去遍历。
举例推导dp数组
以示例1为例，输入：word1 = "horse", word2 = "ros"为例，dp矩阵状态图如下：
参考代码
#include<bits/stdc++.h> using namespace std; int minDistance(string word1, string word2) { vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));//定义dp //初始化 dp[i][0] = i dp[0][j] = j for(int i = 0;i <=word1.size(); i++) { dp[i][0] = i; } for(int j = 0;j <= word2.size(); j++) { dp[0][j] = j; } //递推dp for(int i = 1; i <= word1.size();i++) { for(int j = 1;j <= word2.size(); j++){ if(word1[i-1]==word2[j-1]){//如果相等 dp[i][j] = dp[i-1][j-1];//word1[0,i-1]和word2[0,j-1]的编辑距离 }else{ dp[i][j] = min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1});//不相等,可以word1/word2删除字符,也可以替换当前其中的某个字符. // 增加和删除效果所要编辑的距离是一样的. 所以只需要写一个就好 } } } return dp[word1.size()][word2.size()]; }
647. 回文子串
题目描述
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
思路分析
方法一:暴力法
两层for循环,遍历区间起始位置和终止位置,然后判断这个区间是不是回文.
时间复杂度:O ( n 3 )
方法二:动态规划
确定dp数组以及下标的含义
dp[i] [j]:表示区间范围[i,j]的子串是否是回文子串,如果是dp[i] [j]为true,否则为false.
确定递推顺序
分为两种: 是s[i]与s[j]相等，s[i]与s[j]不相等这两种.
当s[i] 与 s[j]不相等,那么dp[i] [j]一定是false.
当s[i] 与 s[j]相等,分为三种情况
情况一:下标i与j相同,同一个字符例如a,特殊回文子串.
情况二:下标i与j相差为1,例如 aa,也是回文子串
情况三:下标i与j相差大于1的时候,例如cabac,此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1] [j - 1]是否为true。
dp数组如何初始化
dp[i] [j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。
所以dp[i] [j]初始化为false。
确定遍历顺序
遍历顺序可有有点讲究了。
首先从递推公式中可以看出，情况三是根据dp[i + 1] [j - 1]是否为true，在对dp[i] [j]进行赋值true的。
dp[i + 1] [j - 1] 在 dp[i] [j]的左下角，如图：
所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。
举例推导dp数组
举例，输入：“aaa”，dp[i] [j]状态如下：
图中有6个true，所以就是有6个回文子串。
注意因为dp[i] [j]的定义，所以j一定是大于等于i的，那么在填充dp[i] [j]的时候一定是只填充右上半部分。
参考代码
#include<bits/stdc++.h> using namespace std; int countSubstrings(string s) { vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));//j>=i int result = 0;//记录结果集 for(int i = s.size()-1; i >= 0; i--) { for(int j = i; j < s.size(); j++) {//判断子串s[i,j]是否是回文串,首先要满足 j>=i if(s[i]==s[j]) { if(j-i <= 1) { //如果相差小于等于一.则s[i]和s[j] 一定是回文 dp[i][j] = true; result++; } else if(dp[i+1][j-1]) {//如果相差大于1,则判断s[i+1,j-1] 是不是回文,如果是,则s[i,j] 是回文. dp[i][j] = true; result++; } } } } return result; }
516. 最长回文子序列
题目描述
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
思路分析
我们上个题求的是回文子串,这个题求的是回文子序列,要搞清楚这两者之间的区别哦.
回文子串是要连续的，回文子序列可不是连续的！ 回文子串，回文子序列都是动态规划经典题目.
动规五部曲
确定dp数组以及下标的含义
dp[i] [j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i] [j]。
确定递推公式
在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。
如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
如图：
如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i + 1] [j]。
加入s[i]的回文子序列长度为dp[i] [j - 1]。
那么dp[i] [j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
dp数组如何初始化
首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。
所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。
其他情况dp[i][j]初始为0就行
确定遍历顺序
从递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出，dp[i] [j]是依赖于dp[i + 1] [j - 1] 和 dp[i + 1] [j]，
也就是从矩阵的角度来说，dp[i] [j] 下一行的数据。 所以遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的。
递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 分别对应着下图中的红色箭头方向，如图：
举例推导dp数组
输入s:“cbbd” 为例，dp数组状态如图：
红色框即：dp[0] [s.size() - 1]; 为最终结果。
参考代码
