网站四对联广告代码,wordpress可以建站吗,福建建设工程信息网,软件开发商是什么意思算法学习——LeetCode力扣动态规划篇10 583. 两个字符串的删除操作
583. 两个字符串的删除操作 - 力扣#xff08;LeetCode#xff09;
描述
给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个…算法学习——LeetCode力扣动态规划篇10 583. 两个字符串的删除操作
583. 两个字符串的删除操作 - 力扣LeetCode
描述
给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例
示例 1
输入: word1 “sea”, word2 “eat” 输出: 2 解释: 第一步将 “sea” 变为 “ea” 第二步将 eat 变为 “ea”
示例 2:
输入word1 “leetcode”, word2 “etco” 输出4
提示
1 word1.length, word2.length 500 word1 和 word2 只包含小写英文字母
代码解析
动态规划
和1143相同只要求出两个字符串的最长公共子序列长度即可那么除了最长公共子序列之外的字符都是必须删除的最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size()1 , vectorint(word2.size()1 ,0));for(int i0 ;iword1.size() ;i){for(int j0 ;jword2.size() ;j){if(word1[i] word2[j]) dp[i1][j1] dp[i][j] 1;else dp[i1][j1] max(dp[i][j1],dp[i1][j]);}}return word1.size() word2.size() - 2*dp[word1.size()][word2.size()];}
};72. 编辑距离
72. 编辑距离 - 力扣LeetCode
描述
给你两个单词 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’)
提示
0 word1.length, word2.length 500 word1 和 word2 由小写英文字母组成
代码解析
动态规划
确定dp数组以及下标的含义 dp[i][j] 表示前 i 个字符的word1和前 j 个字符的word2最近编辑距离。递推公式 if (word1[ i ] word2[ j ]) 那么说明不用任何编辑 即dp[i1][j1] dp[i ][j ];if (word1[ i ] word2[ j ]) 有三种情况 删除world1 word1第 i 个字符删除一个元素就是world1第 i -1 与world2第 j 再加上一个操作。 即 dp[i1][j1] dp[ i ][ j1] 1;删除world2相当于添加world1 word2第 j 个字符删除一个元素就是world1第 i 与world2第 j -1 再加上一个操作。 即 dp[i1][j1] dp[ i 1][ j] 1;替换元素 word1第 i 个字符和word1第 i -1个字符替换world2同样就是world1第 i -1 与world2第 j -1 再加上一个操作。 即 dp[i1][j1] dp[ i ][ j] 1;最终三种情况取最小 dp[i1][j1] min( dp[i][j] , min(dp[i][j1],dp[i1][j])) 1; dp数组初始化 dp[i][0] 以下标i-1为结尾的字符串word1和空字符串word2最近编辑距离为dp[i][0]。 那么dp[i][0]就应该是i对word1里的元素全部做删除操作即dp[i][0] i; 同理dp[0][j] j;
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size()1 , vectorint(word2.size()1));for(int i0 ; iword1.size();i)dp[i1][0] i1;for(int j0 ; jword2.size();j)dp[0][j1] j1;for(int i0;iword1.size();i){for(int j0; jword2.size();j){if(word1[i] word2[j]) dp[i1][j1] dp[i][j];else dp[i1][j1] min( dp[i][j] , min(dp[i][j1],dp[i1][j])) 1;}}return dp[word1.size()][word2.size()];}
};647. 回文子串
647. 回文子串 - 力扣LeetCode
描述
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
示例
示例 1
输入s “abc” 输出3 解释三个回文子串: “a”, “b”, “c”
示例 2
输入s “aaa” 输出6 解释6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
提示
1 s.length 1000 s 由小写英文字母组成
代码解析
暴力法
class Solution {
public:bool cheak(const string s , int left,int right){for(int ileft ,jright; i(right-left)/2 left; i,j--){if(s[i]!s[j]) return false;}return true;}int countSubstrings(string s) {if(s.size()1) return 1;int num0;int left0,right1;for(int left0 ; lefts.size() ;left){for(rightleft ; rights.size();right){if(cheak(s,left,right)1){num;// coutleft rightendl;}}}return num;}
};
动态规划 确定dp数组dp table以及下标的含义 布尔类型的dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串是否是回文子串如果是dp[i][j]为true否则为false。 确定递推公式 在确定递推公式时就要分析如下几种情况。 当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的区间就是 i1 与 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[i][j]的定义所以j一定是大于等于i的那么在填充dp[i][j]的时候一定是只填充右上半部分。
class Solution {
public:int countSubstrings(string s) {if(s.size()1) return 1;vectorvectorbool dp(s.size(),vectorbool(s.size() , false));int num 0;for(int is.size()-1 ; i0;i--)for(int ji ;js.size();j)//s[i]s[j]为首尾相同//并且j-i 1为a或者aa的情况,为回文串//如果j-i不是1,但是dp[i1][j-1]true也是回文串因为首位相同中间是回文串//如dabcd首位d相同中间dp[i1][j-1]为abc也是回文串即dabcd为回文串if( s[i]s[j] (j-i 1||dp[i1][j-1]true) ) {num;dp[i][j] true;}return num;}
};516. 最长回文子序列
516. 最长回文子序列 - 力扣LeetCode
描述
给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
示例
示例 1
输入s “bbbab” 输出4 解释一个可能的最长回文子序列为 “bbbb” 。
示例 2
输入s “cbbd” 输出2 解释一个可能的最长回文子序列为 “bb” 。
提示
1 s.length 1000 s 仅由小写英文字母组成
代码解析
动态规划 确定dp数组dp table以及下标的含义 dp[i][j]字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。 确定递推公式 在判断回文子串的题目中关键逻辑就是看s[i]与s[j]是否相同。 如果s[i]与s[j]相同 j - i 0 , dp[i][j] 1;j - i 1, dp[i][j] 2;j - i 2, dp[i][j] dp[i 1][j - 1] 2; 如果s[i]与s[j]不同 dp[i][j] max(dp[i 1][j], dp[i][j - 1]); 确定遍历顺序 从递推公式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的时候一定要从下到上遍历这样才能保证下一行的数据是经过计算的。
class Solution {
public:int longestPalindromeSubseq(string s) {if(s.size()1) return s.size();vectorvectorint dp(s.size() , vectorint(s.size() ,0));int result 0;for(int is.size()-1; i0 ;i-- )for(int ji ;js.size();j){if(s[i]s[j]){if(ji) dp[i][j] 1;else if(j-i1) dp[i][j] 2;else dp[i][j] dp[i1][j-1] 2;if(dp[i][j] result) result dp[i][j];}else{dp[i][j] max(dp[i][j-1],dp[i1][j]);}}// for(int i0;is.size();i)// {// for(int j0;js.size();j)// coutdp[i][j] ;// coutendl;// }return result;}
};
