Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
/*和712题Minimum ASCII Delete Sum for Two Strings基本一模一样，都是调整两个字符串到相等，一看不需要过程只要步数，就是动态规划 从两个字符串的开头开始比较，一个一个比较，我们用二维数组dp[i][j]代表字符串1前i个字符和字符串2前j个字符调整到相同时，str1所需要调整的步数 有三种方法可以到达dp[i][j]: 1.dp[i-1][j] + 1:由于从dp[i-1][j]到dp[i][j]是多考虑了str1的一个字符，但是str2字符数没变，所以要想相同，必须删除str[i],步骤+1 2.dp[i][j-1] + 1:对应于1，这个是多考虑str2的一个字符，所以str1应该添加上，步骤+1 3.dp[i-1][j-1] + a，这里是考虑两个str都加了一个，所以str1[i] =str2[j]时，a=0；str1[i] ！=str2[j]时，str1[i]应该改成str2[j]，a=1 这三种情况每次比较出最小的来，最后返回dp[str1.length][str2.length](这里字符串下标从1开始，因为我们考虑dp数组的第0行代表str1还啥也没有，第0列代表str2啥也没有) */ public int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); int[][] dp = new int[m+1][n+1]; //初始化动态数组，就是第0行数据和第1行数据,注意由于下标从1开始，所以charAt的时候要-1 for (int i = 1;i < m+1;i++) dp[i][0] = dp[i-1][0] + 1; for (int i = 1;i < n+1;i++) dp[0][i] = dp[0][i-1] + 1; for (int i = 1;i < m+1;i++) { for (int j = 1;j < n+1;j++) { //先看word1[i]和word2[j]是不是相等，确定a int a =(word1.charAt(i-1) == word2.charAt(j-1))? 0 : 1; //比较三种情况 dp[i][j] = Math.min(dp[i-1][j-1]+a,Math.min(dp[i-1][j] + 1,dp[i][j-1] + 1)); } } return dp[m][n];