[Lc]72编辑距离

题目

题解

• 时间复杂度$O(mn)$
• 空间复杂度$O(mn)$，都是搞dp数组用的

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n=word1.size(), m=word2.size();
        if(n*m==0) return n+m;//若一个为空，返回另一个的长度
        int dp[n+1][m+1];//初始化dp数组

        for(int i=0; i<n+1; ++i) dp[i][0] = i;
        for(int i=0; i<m+1; ++i) dp[0][i] = i;//初始化其中一个为空字符串时的dp数组中的值

        for(int i=1; i<n+1; ++i){
            for(int j=1; j<m+1; ++j){
                int left = dp[i-1][j]+1;
                int up = dp[i][j-1]+1;//左边和上面的分别加一
                //左上的要分情况讨论，若两个字母最后一个，相同，则不用加一
                int left_up = word1[i-1]==word2[j-1]? dp[i-1][j-1]:dp[i-1][j-1]+1;
                //取三个里面最小冬天规划
                dp[i][j] = min(left_up, min(left,up));
            }
        }
        return dp[n][m];
    }
};