网站的基本价格,官方网站建设公司,网站页面类型,科技学堂文章目录题目描述思路 代码 O(n2n^2n2)、O(n2n^2n2)二刷打卡第十三天#xff5e; 题目描述
感觉和正则表达式匹配这道题很像#xff1a;同样的两个字符串#xff0c;同样的二维数组dp#xff0c;同样的hard。。
思路 代码 O(n2n^2n2)、O(n2n^2n2…
文章目录题目描述思路 代码 O(n2n^2n2)、O(n2n^2n2)二刷打卡第十三天 题目描述
感觉和正则表达式匹配这道题很像同样的两个字符串同样的二维数组dp同样的hard。。
思路 代码 O(n2n^2n2)、O(n2n^2n2)
使用动态规划的做法同样多开一行、一列来进行边界处理。dp[i][j]以[0, i] 和 [0, j]的子串word1Son转化成word2Son的最少操作数字具体做法见注释的 part 和 Case主要代码应该是注释 part 2.2 部分的代码可以这么理解 0. 对于当前 dp[i][j] 的选取值i、j匹配的情况显而易见是直接选取dp[i - 1][j - 1]最优 不匹配的情况有三个最优子结构左边的dp[i][j - 1]上边的dp[i - 1][j]以及左上的dp[i -1][j - 1]。经过思考我们可以发现这三个最优子结构可以分别通过增、删、减的方式操作数 1转移到 dp[i][j] 的状态。那么显而易见选取三个子结构的最小值再增加一个操作数就是当前的最优选择
class Solution {public int minDistance(String word1, String word2) {// initint m word1.length();int n word2.length();// dp[i][j]:以[0, i] 和 [0, j]的子串word1Son转化成word2Son的最少操作数字int[][] dp new int[m 1][n 1];// part 1边界// part 1.1: 直接插入for(int i 0; i n; i) {dp[0][i] i;}// part 1.2: 直接删除for(int i 0; i m; i) {dp[i][0] i;}// part 2具体规划过程for(int i 1; i m; i) {for(int j 1; j n; j) {// part 2.2: 当前字符不匹配if(word1.charAt(i - 1) ! word2.charAt(j - 1)) {// Case 1: 删除当前i字符 dp[i - 1][j]删// Case 2: dp[i][j - 1] 插入j字符插// Case 3: dp[i - 1][j - 1] i 和 j 对着替换一个。替// 三种选择选取步骤最少的一个dp[i][j] Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) 1;}// part 2.1: 直接匹配不用操作else {dp[i][j] dp[i - 1][j - 1];}}}return dp[m][n];}
}二刷
一如既往地明了有效代码其实就12行
class Solution {public int minDistance(String word1, String word2) {// dp[i][j]把 word1[0][i] 变成 word2[0][j] 需要的步数int[][] dp new int[word1.length() 1][word2.length() 1]; // 直接删成 word2for(int i 0; i word1.length(); i) {dp[i][0] i;}// 直接插成 word2for(int i 0; i word2.length(); i) {dp[0][i] i;}for(int i 1; i word1.length(); i) {for(int j 1; j word2.length(); j) {// 相等相当于不用动直接取上一阶的结果if(word1.charAt(i - 1) word2.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1];}// 不相等取改、删、插的最小值 1.else {dp[i][j] Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) 1;}}}return dp[word1.length()][word2.length()];}
}
