Leetcode 72. Edit Distance (python+cpp)

题目

解析：

这道题目是著名的Levenshtein distance问题，解法当然是动态规划。本题的关键主要是找出三种操作1.insert 2.delete 3. replace这三种操作与动态规划sub problem之间的关系。首先定义一个二维dp数组，dp[i][j]代表将word1[0:i]编辑成word2[0:j]所需要的最短距离。接下来具体分析三种操作与sub problem之间的对应。

• insert操作，insert意味着在word1[0:i]后面加一个字符，这意味着，他不影响word1[0:i],但是这部操作解决了word2第j个字符的distance，所以说现在的sub problem依旧是word1[0:i]到word2[0:j-1]换言之dp[i][j-1]
• replace操作，同样的分析replace操作对应的subproblem应该是dp[i-1][j-1]
• delete操作对应的是dp[i-1][j]
• 而对于某种状态应该分为两种情况，如果当前的word中的当前字符相同，意味着这个位置不需要任何操作。如果不同，那应该采取上面上述操作中最小的一种
  综上所述，最后的状态转移方程应该如下：

if word1[i-1]==word2[j-1]：dp[i][j] = dp[i-1][j-1] // 无需任何操作
else:dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])) + 1 // 去三种操作中对应sub problem最小的一个

更详细的解析推荐看这个youtube视频，确实讲的非常好
https://www.youtube.com/watch?v=MiqoA-yF-0M

python代码如下：

class Solution:def minDistance(self, word1: str, word2: str) -> int:m,n = len(word1),len(word2)if m*n == 0:return m+ndp = [[0]*(n+1) for _ in range(m+1)]for i in range(m+1):for j in range(n+1):if i==0:dp[i][j] = jelif j==0:dp[i][j] = ielif word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1return dp[-1][-1]

C++代码如下：

class Solution {
    
public:int minDistance(string word1, string word2) {
    int m = word1.size(),n = word2.size();if (m*n==0) return m+n;vector<vector<int>> dp(m+1,vector<int>(n+1,0));for (int i=0;i<=m;i++){
    for (int j=0;j<=n;j++){
    if (i==0){
    dp[i][j] = j;}else if(j==0){
    dp[i][j] = i;}else if(word1[i-1]==word2[j-1]){
    dp[i][j] = dp[i-1][j-1];}else{
    dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])) + 1;}}}return dp[m][n];}
};