Calculate the distance between two strings
temp.s and
temp.t.
This is an implementation of the dynamic programming approach. Time complexity of O(m*n).
For an explanation of the algorithm, see the Wikipedia article.
PHP Code:
function levenshtein(temp.s, temp.t) {
temp.m = temp.s.length();
temp.n = temp.t.length();
temp.d = new[temp.m][temp.n];
for (temp.i = 0; temp.i <= temp.m; temp.i++) {
temp.d[temp.i][0] = temp.i;
}
for (temp.j = 0; temp.j <= temp.n; temp.j++) {
temp.d[0][temp.j] = temp.j;
}
for (temp.j = 1; temp.j <= temp.n; temp.j++) {
for (temp.i = 1; temp.i <= temp.m; temp.i++) {
if (temp.s.charat(temp.i-1) == temp.t.charat(temp.j-1)) {
temp.d[temp.i][temp.j] = temp.d[temp.i-1][temp.j-1];
} else {
temp.d[temp.i][temp.j] = min(temp.d[temp.i-1][temp.j] + 1
, min(temp.d[temp.i][temp.j-1] + 1, temp.d[temp.i-1][temp.j-1] + 1)
);
}
}
}
return temp.d[temp.m-1][temp.n-1];
}
e.x.,
PHP Code:
echo(levenshtein("kitten", "sitting")); // echos 3
echo(levenshtein("Saturday", "Sunday")); // echos 3
echo(levenshtein("unixmad", "Stefan")); // echos 5