3 ms·
furthermore its not even the dynamic implementation. m[i,j] = d(s1[1..i], s2[1..j]) m[0,0] = 0 m[i,0] = i, i=1..|s1| m[0,j] = j, j=1..|s2| m[i,j] = min(m[i-1,
by leecarraher 11y ago
furthermore its not even the dynamic implementation.
m[i,j] = d(s1[1..i], s2[1..j])
m[0,0] = 0
m[i,0] = i, i=1..|s1|
m[0,j] = j, j=1..|s2|
m[i,j] = min(m[i-1,j-1]
+ if s1[i]=s2[j] then 0 else 1 fi,
m[i-1, j] + 1,
m[i, j-1] + 1 ), i=1..|s1|, j=1..|s2|