My clear C++ dp solution


  • 0
    F
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            if(word1.size()==0||word2.size()==0) return word1.size()==0?word2.size():word1.size();
            int dp[word1.size()][word2.size()]={0};
            if(word1[0]==word2[0]) dp[0][0]=0;
            else dp[0][0]=1;
            bool flag=false;
            for(int i=1;i<word1.size();i++){
                if(word1[i]==word2[0]&&flag== false) {
                    flag=true;
                    dp[i][0]=dp[i-1][0];
                }else dp[i][0]=dp[i-1][0]+1;
            }
            flag=false;
            for(int j=1;j<word2.size();j++){
                if(word2[j]==word1[0]&&flag== false) {
                    flag=true;
                    dp[0][j]=dp[0][j-1];
                }else dp[0][j]=dp[0][j-1]+1;
            }
            for(int i=1;i<word1.size();i++){
                for(int j=1;j<word2.size();j++){
                    if(word1[i]==word2[j]){
                        dp[i][j]=dp[i-1][j-1];
                    }else{
                        dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                    }
                }
            }
            return dp[word1.size()-1][word2.size()-1];
        }
    };
    

Log in to reply
 

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