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(给定两个单词Word 1和Word2，找到将word 1转换为Word2所需的最小步骤数(每个操作都算作1步)。 允许对一个单词进行以下3种操作： (A)插入一个字符 (B)删除字符 (C)替换字符)
思路:利用动态规划思想，dp[i][j]代表由word1前i位变为word2前j位所需要的最短步数分为两种情况。
1.word1[i]等于word2[j],那么此时此刻不需要进行任何多余操作，由word1前i位变为word2前j位所需要的最短步数为由word1前i-1位变为word2前j-1位所需要的最短步数，即dp[i][j]=dp[i-1][j-1].2.word1[i]不等于word2[j]，那么此时可以进行三种操作来完成转换功能。假设word1的前i位为XXX1，word2的前j位为YYY2. (1)使用替换操作,直接将1替换为2，那么此时的步数为word1前i-1位变为word2前j-1位所需要的最短步数加上这次替换操作,即dp[i-1][j-1]+1。 (2)使用插入操作,将XXX1先转化为YYY,之后再插入一个2，此时的步数为word1前i位变为word2前j-1位所需要的最短步数加上这次插入操作,即dp[i][j-1]+1。 (3)使用删除操作,将XXX转化为YYY2，再将最后面的1删除,此时的步数为word1前i-1位变为word2前j位所需要的最短步数加上这次删除操作,即dp[i-1][j]+1。最后找到这三种操作产生操作数中的最小操作数即为dp[i][j]的值。
public class Edit_Distance { public static int minDistance(String word1, String word2) { int length1 = word1.length(); int length2 = word2.length(); int dp[][] = new int[length1+1][length2+1]; for(int i=0;i<=length1;i++) { dp[i][0] = i; } for(int i=0;i<=length2;i++) { dp[0][i] = i; } for(int i=1;i<=length1;i++) { for(int j=1;j<=length2;j++) { if(word1.charAt(i-1)==word2.charAt(j-1)) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = Math.min(Math.min(dp[i][j-1]+1,dp[i-1][j]+1),dp[i-1][j-1]+1); } } } return dp[length1][length2]; } public static void main(String[] args) { String word1 = "BCD"; String word2 = "CDE"; System.out.println(minDistance(word1, word2)); } }