72. Edit Distance

Question

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Solution

本题和583. Delete Operation for Two Strings大同小异。

动态规划，两个字符串的分别以长宽组成一个矩阵，记录该位置得编辑距离。
将初始的编辑距离dp[i][0]一行和dp[0][j]一列按照对应的位置i和j填写。

双重遍历矩阵的坐标。
当两个字符相等时，编辑距离等于对角线方向的状态的编辑距离（即两个字符都没有取得上一个状态）。
当两个字符不相等时，编辑距离等于左边，上边（少取一个字符的状态）以及对角线方向（两个字符都不取的状态）的编辑距离中得最小值再加上1。

Code

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