72. Edit Distance

Published on March 5, 2023

问题

参考算法导论动态规划的介绍。

解析

参考算法导论动态规划的介绍。这个题目是我上算法课的时候老师揉碎了讲的一个例子，并且在期末考试也做了变形。详细的题目描述和解析以及经典的状态转移的表格，建议去看一下《算法导论》这本书。

代码

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];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        
        for (int i = 1; i <= n; i++) {
            dp[0][i] = i;
        }
        
        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] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
            }
        }
        return dp[m][n];
    }
}

Problem

Refer to the introduction to dynamic programming in Introduction to Algorithms.

Solution

Refer to Introduction to Dynamic Programming in Algorithms. This topic is an example that was crumpled up in my algorithms class and deformed in the final exam. For a detailed description and analysis of the topic, as well as a table of classical state transfers, it is recommended to look at the book Introduction to Algorithms.

Code

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];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        
        for (int i = 1; i <= n; i++) {
            dp[0][i] = i;
        }
        
        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] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
            }
        }
        return dp[m][n];
    }
}