c++ solution w/ brief explaination


  • 1
    B

    dp[i][j] represents the minium operations needed of word1.substr(i) and word2.substr(j).
    Thus, we have 3 ways to get dp[i][j]:

    1. insert: dp[i][j]=dp[i][j-1]+1
    2. delete: dp[i][j]=dp[i-1][j]+1
    3. replace: dp[i][j]=dp[i-1][j-1]+1

    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int m=word1.size(),n=word2.size();
            if(!m || !n) return m+n;
            vector<vector<int>> dp(m+1,vector<int>(n+1,0));
            
            //intialize
            for(int i=0;i<=n;i++) dp[0][i]=i;
            for(int i=0;i<=m;i++) dp[i][0]=i;
            
            //transition
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    if(word1[i-1]!=word2[j-1])
                        dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                    else 
                        dp[i][j]=dp[i-1][j-1];
                }
            }
            
            return dp[m][n];
        }
    };
    

Log in to reply
 

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