[数据结构与算法]【每日一题】LeetCode72. 编辑距离【线性DP】

思路

状态：dp[i][j]表示word1的前i个字符变成word2的前j个字符的最少操作数。
状态转移方程

• word[i]==word[j]–>dp[i][j] = dp[i-1][j-1]
• word[i]!=word[j] 需要考察，修改，插入，删除三种情况取最小值
  
• f[i][j] = min(f[i-1][j-1],min(f[i][j-1],f[i-1][j]))+1

AC代码

C++

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

Python

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