编辑距离

编辑距离

int minDistance(string &word1, string &word2) {
    int n = word1.size(),m=word2.size();
    int dp[n+1][m+1];
    for(int i=0;i<=n;i++){
        dp[i][0] = i;
    }
    for(int i=0;i<=m;i++){
        dp[0][i]=i;
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(word1[j-1]==word2[i-1]){
                dp[j][i]=dp[j-1][i-1];
            }else{
                int a = dp[j-1][i-1]+1;
                int b = dp[j][i-1]+1;
                int c  =dp[j-1][i]+1;
                if(a>b) a=b;
                if(a>c) a=c;
                dp[j][i]=a;
            }
        }
    }
    return dp[n][m];
}