same as LCS problem


  • 0
    X
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int m=word1.size(),n=word2.size();
            //最长公共 LCS
            vector<vector<int>> dp(m+1,vector<int>(n+1,0));
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1]+1;
                    else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }//end for
            return m+n - 2*dp[m][n];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.