河源哪里做网站,网站建设服务器软件,网页升级紧急通知app下载,广州市软件开发有限公司力扣爆刷第133天之动态规划收尾#xff08;距离编辑与回文子串#xff09; 文章目录 力扣爆刷第133天之动态规划收尾#xff08;距离编辑与回文子串#xff09;一、72. 编辑距离二、647. 回文子串三、516. 最长回文子序列 一、72. 编辑距离
题目链接#xff1a;https://l…力扣爆刷第133天之动态规划收尾距离编辑与回文子串 文章目录 力扣爆刷第133天之动态规划收尾距离编辑与回文子串一、72. 编辑距离二、647. 回文子串三、516. 最长回文子序列 一、72. 编辑距离
题目链接https://leetcode.cn/problems/edit-distance/description/ 思路本题也是前面重复子序列的变体可以对字符串进行增删替换操作其中增加和删除是一样的而替换依赖的是前一个位置。 定义dp[i][j]表示以下标i为结尾的word1和以下标j为结尾的word2要相等所需要的操作。 如果word1[i] word2[j]那么所需次数依赖于word1[i-1]和word2[j-1]即dp[i][j] dp[i-1][j-1]。 如果word1[i] ! word2[j]那么增删对应的都是dp[i-1][j]dp[i][j-1]替换对应的是dp[i-1][j-1]取三者最低。
class Solution {public int minDistance(String word1, String word2) {int m word1.length(), n word2.length();int[][] dp new int[m1][n1];for(int i 0; i m; i) dp[i][0] i;for(int i 0; i n; i) dp[0][i] i;for(int i 0; i m; i) {for(int j 0; j n; j) {if(word1.charAt(i) word2.charAt(j)) {dp[i1][j1] dp[i][j];}else{dp[i1][j1] Math.min(Math.min(dp[i1][j], dp[i][j1]), dp[i][j]) 1;}}}return dp[m][n];}
}
二、647. 回文子串
题目链接https://leetcode.cn/problems/palindromic-substrings/description/ 思路 常规做法本题求回文子串的个数子串是要求连续的我们可以从单点和双点向字符串两段遍历并且记录下子串的个数。 也可以使用动态规划定义dp[i][j]表示区间s[i,j]是回文子串dp[i][j]依赖于dp[i1][j-1]也就是当前位置的左下方。
class Solution {public int countSubstrings(String s) {int sum 0;for(int i 0; i s.length(); i) {sum countSum(s, i, i);sum countSum(s, i, i1);}return sum;}int countSum(String s, int i, int j) {int count 0;while(i 0 j s.length()) {if(s.charAt(i) s.charAt(j)) {count;i--;j;}else{break;}}return count;}}
动态规划解法
class Solution {public int countSubstrings(String s) {int len s.length(), sum 0;boolean[][] dp new boolean[len][len];for(int i len-1; i 0; i--) {for(int j i; j len; j) {if(s.charAt(i) s.charAt(j) (j-i2 || dp[i1][j-1])) {dp[i][j] true;sum;}}}return sum;}
}
三、516. 最长回文子序列
题目链接https://leetcode.cn/problems/longest-palindromic-subsequence/ 思路上一题求的是回文子串的个数本题求的是回文子序列的长度一个连续一个不连续。定义dp[i][j]表示区间[i, j]中的最长回文子序列的长度是dp[i][j]例如a b b b a的长度依赖于 bbb中回文子序列的长度所以遍历的方式是从下往下从左往右。s[i] s[j]时依赖于左下角的元素dp[i][j] dp[i1][j-1]s[i] ! s[j]时就类似于a b b b 或者 b b b a即dp[i][j] Math.max(dp[i][j-1], dp[i1][j]);
class Solution {public int longestPalindromeSubseq(String s) {int len s.length();int[][] dp new int[len][len];for(int i 0; i len; i) dp[i][i] 1;for(int i len-1; i 0; i--) {for(int j i1; j len; j) {if(s.charAt(i) s.charAt(j)) {dp[i][j] dp[i1][j-1] 2;}else{dp[i][j] Math.max(dp[i][j-1], dp[i1][j]);}}}return dp[0][len-1];}
}
