My C++ code with comments, DP using an array [2][word1.size()+1]


  • 0
    D
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            const int len1 = word1.size();
            const int len2 = word2.size();
            
            if(!len1 || !len2) return max(len1, len2); // one is an empty string, then just delete
            
            int op[2][len1+1]; // work in ping-pong mode
            int i, j, cur, next;
            
            for(i=0;i<=len1;i++)  op[0][i]=i; // delete, op[0][i] means the number of op that make word1[0:i-1] match with word2[0:-1] (i.e.empty sub-string) 
    
            for(j=0; j<len2;j++)
            {
                cur = j%2; // ping-pong switch
                next = 1 - cur;
                
    // op[cur][i] is the number of op that make word1[0:i-1] match with word2[0:j-1]  
    // op[next][i] is the number of op that make word1[0:i-1] match with word2[0:j]
    // if word1[i-1]==word2[j], then op[next][i] = op[cur][i-1];
    // if word1[i-1]!=word2[j], then op[next][i] = min(op[cur][i-1] (i.e. replace),op[next][i-1] (delete), op[cur][i] (insert)) + 1;
                op[next][0]= op[cur][0] + 1; //insert
                for(i=1;i<=len1;i++)
                {
                    if(word1[i-1]!=word2[j])
                    {
                        op[next][i] = min(op[cur][i-1], op[next][i-1]); // delete
                        op[next][i] = min(op[next][i], op[cur][i]) + 1; // insert
                    }
                    else
                        op[next][i] = op[cur][i-1];
                }
            }
            return op[next][len1];
            
        }
    };

Log in to reply
 

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