72. 编辑距离

题目

参考72. 编辑距离。

解题思路

• 动态规划：需要知道插入和删除的代价是一样的，所以题目其实只有两种情况，插入和修改，两个字符串比较时如果相同代价不变否则取前一个最小+1。
• 记忆化搜索：使用记忆化搜索也可实现，速度更快。

动态规划 4ms

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        char[] w1 = word1.toCharArray(), w2 = word2.toCharArray();
        //考虑动态规划 dp[i][j]表示word1[0-i]转化为word2[0-j]所使用的最少操作次数
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 0;
        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(w1[i-1]==w2[j-1]) dp[i][j] = dp[i-1][j-1];
                else {
                    dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j-1]+1);
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

记忆化搜索 2ms

class Solution {
    char[] w1,w2;
    int[][] memo;
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        w1 = word1.toCharArray();
        w2 = word2.toCharArray();
        memo = new int[m+1][n+1];//记忆化搜索优化
        return dfs(m,n);
    }

    int dfs(int i,int j) {
        if(i == 0) return j;
        if(j == 0) return i;
        if(memo[i][j] != 0) return memo[i][j];
        if(w1[i-1] == w2[j-1]) return memo[i][j] = dfs(i-1,j-1);
        int res = Math.min(dfs(i-1,j),dfs(i,j-1));
        return memo[i][j] = Math.min(res,dfs(i-1,j-1)) + 1;
    }
}

复杂度分析

• 时间复杂度：O(mn)，m/n分别为两个字符串的长度。
• 空间复杂度：O(mn)。