leetcode 72. Edit Distance
编辑距离，动态规划
public class Solution { public int minDistance(String word1, String word2) { int l_1 = word1.length(); int l_2 = word2.length(); // if(l_1==0) return l_2; // if(l_2==0) return l_1; int[][] dp = new int[l_1+1][l_2+1]; for(int i=1;i<=l_1;i++){ dp[i][0]=i; } for(int j=1;j<=l_2;j++){ dp[0][j]=j; } for(int i=1;i<=l_1;i++){ for(int j=1;j<=l_2;j++){ //replace if(word1.charAt(i-1)==word2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = dp[i-1][j-1] + 1; } //insert dp[i][j] = dp[i][j]<(dp[i][j-1]+1)?dp[i][j]:(dp[i][j-1]+1); //delete dp[i][j] = dp[i][j]<(dp[i-1][j]+1)?dp[i][j]:(dp[i-1][j]+1); } } return dp[l_1][l_2]; } }