本文主要是介绍力扣爆刷第133天之动态规划收尾(距离编辑与回文子串),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣爆刷第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[m+1][n+1];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[i+1][j+1] = dp[i][j];}else{dp[i+1][j+1] = Math.min(Math.min(dp[i+1][j], dp[i][j+1]), 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[i+1][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, i+1);}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-i<=2 || dp[i+1][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[i+1][j-1],s[i] != s[j]时,就类似于a b b b 或者 b b b a,即dp[i][j] = Math.max(dp[i][j-1], dp[i+1][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 = i+1; j < len; j++) {if(s.charAt(i) == s.charAt(j)) {dp[i][j] = dp[i+1][j-1] + 2;}else{dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);}}}return dp[0][len-1];}
}
这篇关于力扣爆刷第133天之动态规划收尾(距离编辑与回文子串)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!