Edit Distance

给两个字符串和三种操作, 添加/删除/替换其中一个字符. 问怎么最少的操作得到另一个字符串. 这个是经典算法. 用dp做, dp[i][j] 代表在w1的i和w2的j的最少操作.

public class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        int[][]dp = new int[n+1][m+1];
        for(int i = 0 ; i < m+1; i++) 
            dp[0][i] = i;
        for(int i = 0 ; i < n+1; i++)
            dp[i][0] = i;
        
        for(int i = 1; i < n+1; i++){
            for(int j = 1; j < m+1; j++) {
                if(word1.charAt(i-1) == word2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
            }
        }
        return dp[n][m];
    }
}