Edit Distance (Levenshtein)

dynamic programming

Best O(n · m)Avg O(n · m)Worst O(n · m)Space O(n · m)

Preparing Edit Distance (Levenshtein)...

Computes minimum insertions, deletions, and substitutions needed to transform word1 into word2.