72. Edit Distance

Given two wordsword1andword2, find the minimum number of steps required to convertword1toword2. (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

思路：DP，还是比较烦。不会考

public class Solution {
    public int minDistance(String word1, String word2) {

        int nRows = word1.length();
        int nCols = word2.length();

        int[][] dp = new int[nRows+1][nCols+1];

        for (int i=0;i<=nRows;i++){
            dp[i][0] = i;
        }

        for (int j=0;j<=nCols;j++){
            dp[0][j] = j;
        }

        for (int i=0;i<nRows;i++){
            char c1 = word1.charAt(i);
            for (int j=0;j<nCols;j++){
                char c2 = word2.charAt(j);
                if (c1==c2){
                    dp[i+1][j+1] = dp[i][j];
                }else{
                    int replace = dp[i][j]+1;
                    int insert = dp[i][j+1]+1;
                    int delete = dp[i+1][j]+1;

                    int min = replace > insert ? insert : replace;
                    min = delete > min ? min : delete;
                    dp[i + 1][j + 1] = min; 
                }
            }
        }
        return dp[nRows][nCols];
    }
}