题解 | #编辑距离(一)#
编辑距离(一)
https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da
public class Solution { /** * 编辑距离——将 str1 转换为 str2 所要的最少操作数 * @param str1 字符串1 * @param str2 字符串2 * @return 最少操作数 */ public int editDistance (String str1, String str2) { int n1 = str1.length(); int n2 = str2.length(); // int[][] dp = new int[n1 + 1][n2 + 1]; // 初始化 for (int i = 1; i <= n1; ++i) { dp[i][0] = dp[i - 1][0] + 1; } for (int i = 1; i <= n2; ++i) { dp[0][i] = dp[0][i - 1] + 1; } // 递推方程式 for (int i = 1; i <= n1; ++i) { for (int j = 1; j <= n2; ++j) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 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[n1][n2]; } }
dp算法牛