leetcode编辑距离

leetcode题目链接

博客讲解链接
b站视频讲解得很清晰

leetcode C++通过代码：

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