题解 | 编辑距离(一)

#include <vector>
class Solution {
public:
    /**
     * dp[i][j] str1[1]——[i] str2[1]——[j]的操作数
     * 1.str1 str2 的长度差每增加一个，操作数加一个
     * 2.不同的修改操作+1，否则保持
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    int editDistance(string str1, string str2) {
        // write code here
        int len1=str1.length();
        int len2=str2.length();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
// 1.str1 str2 的长度差每增加一个，操作数加一个
//这里极端情况，str1=0 or str2=0
        for(int i=1;i<=len1;i++)
            dp[i][0]=dp[i-1][0]+1;
        for(int i=1;i<=len2;i++)
            dp[0][i]=dp[0][i-1]+1;
//相同的保持，不同的修改操作+1  
        for(int i=1;i<=len1;i++){
            for (int j=1; j<=len2; j++) {
                if(str1[i-1]==str2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    //前一个最少操作的状态
                    //修改 dp[i-1][j-1]
                    //增加 dp[i-1][j]
                    //删除 dp[i-1][j]
                    dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }
        }
        return dp[len1][len2];

    }
};