LeetCode72编辑距离

题目描述

解析

  一般这种给出两个字符串的动态规划问题都是维护一个二维数组，尺寸和这两个字符串的长度相等，用二维做完了后可以尝试优化空间。这一题其实挺类似1143这题的，只不过相比1143的一种方式，变成了三种方式，就要找三个值，在其中取最小的那一个。

public static int minDistance(String word1, String word2) {char[] w1 = word1.toCharArray();char[] w2 = word2.toCharArray();int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];// 初始化第一行和第一列for (int i = 0; i <= len1; i++) {dp[i][0] = i;}for (int j = 0; j <= len2; j++) {dp[0][j] = j;}// 填充dp数组for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {int cost = (w1[i - 1] == w2[j - 1]) ? 0 : 1;dp[i][j] = Math.min(dp[i - 1][j] + 1, // 删除Math.min(dp[i][j - 1] + 1, // 插入dp[i - 1][j - 1] + cost)); // 替换}}return dp[len1][len2];}