8 ms solution in C

• ``````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];
}``````

• ``````u = ret[j-1];
``````

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

• int ret[s2];
Is this right?

• 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.

• I understand, thank you for your explanation. √

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