动态规划之编辑距离.md

动态规划之编辑距离

递归解法

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        return dp(word1, m-1, word2, n-1);
    }

    private int dp(String s1, int i, String s2, int j) {
        if (i == -1) {
            return j + 1;
        } else if (j == -1) {
            return i + 1;
        }

        if (s1.charAt(i) == s2.charAt(j)) {
            return dp(s1, i-1, s2, j-1); // skip
        } else {
            return min(
                dp(s1, i, s2, j-1) + 1, // insert
                dp(s1, i-1, s2, j) + 1, // delete
                dp(s1, i-1, s2, j-1) + 1 // replace
            );
        }
    }

    private int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

动态规划

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        int[][] dp = new int[m+1][n+1]; // 将word1[0...m-1]转换成word2[0...n-1]所需的最小操作数
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else 
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
            }
        }
        return dp[m][n];
    }

    private int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}