8 ms solution in C


  • 0
    Y
    int minDistance(char* word1, char* word2) {
        int s1 = strlen(word1);
        int s2 = strlen(word2);
        if (s1 == 0 || s2 == 0) return s1 + s2;
        int ret[s2];
        int i,j,p,q,s,t,u;
        for (j = 0; j < s2; ++j) ret[j] = j+1; // n of steps to go from empty string to word2[:j]
        for (i =0; i < s1; ++i){
            char c1 = word1[i];
            for (j =0; j < s2; ++j) {
                char c2 = word2[j];
                q = ret[j]; // save the ret[j-1] from previous i iteration for the next j iteration
                if (c1 == c2) ret[j] = (j==0) ? i : p; // if 2nd str has a single char, n steps = len(1st str) - 1, since last chars cancel
                else{ // find min of three possible previous dp steps: (i-1,j), (i,j-1), and (i-1,j-1), each + 1
                    u = ret[j-1];
                    s = ( (j==0) ? i: (u > p ? p : u ) ) ; 
                    t = ret[j];
                    ret[j] = ( s > t ? t : s ) + 1;
                }
                p = q; 
            }
        }
        return ret[s2-1];
    }

  • 0
    F
    u = ret[j-1];
    

    if c1 != c2, and j = 0, the code above will be run as u = ret[-1]; why it can work?


  • 0
    R

    int ret[s2];
    Is this right?


  • 0
    Y

    You are right this could be made better, for instance, by substituting all occurrences of u with ret[-1] in the following line. But the reason it works is that when j==0, u is not used. ret[-1] is the same as ret - 1, which unless in very edge case won't throw an error.


  • 0
    F

    I understand, thank you for your explanation. √


Log in to reply
 

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