package dp.minDistance; /** * 72. 编辑距离 * 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 * * 你可以对一个单词进行如下三种操作: * * 插入一个字符 * 删除一个字符 * 替换一个字符 * * * 示例 1: * * 输入:word1 = "horse", word2 = "ros" * 输出:3 * 解释: * horse -> rorse (将 'h' 替换为 'r') * rorse -> rose (删除 'r') * rose -> ros (删除 'e') * 示例 2: * * 输入:word1 = "intention", word2 = "execution" * 输出:5 * 解释: * intention -> inention (删除 't') * inention -> enention (将 'i' 替换为 'e') * enention -> exention (将 'n' 替换为 'x') * exention -> exection (将 'n' 替换为 'c') * exection -> execution (插入 'u') * * * 提示: * * 0 <= word1.length, word2.length <= 500 * word1 和 word2 由小写英文字母组成 */ public class minDistance { public static int minDistance(String word1, String word2) { int len1 = word1.length(); int len2 = word2.length(); char[] char1 = word1.toCharArray(); char[] char2 = word2.toCharArray(); int[][] dp = new int[len1 + 1][len2 + 2]; //初始化 for (int i = 0; i <=len1; i++) { dp[i][0] = i; } for (int i = 0; i <=len2; i++) { dp[0][i]=i; } //相同就跳过,否则就取三种操作中最小的 for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (char1[i - 1] == char2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1); } } } return dp[len1][len2]; } public static void main(String[] args) { String word1 = "horse", word2 = "ros"; System.out.println(minDistance(word1, word2)); } }
不会,我可以学;落后,我可以追赶;跌倒,我可以站起来!