What is edit distance?

The edit distance is the minimum number of changes required to convert string1 to string2. This conversion can be brought on by:

• Insertion
• Removal
• Replacement

The time complexity for all three of these processes is $O(1)$. As shown in the illustration below, only the last word from string1 (p) needs to be replaced with d to make the two strings equal.

Approach

Dynamic programming is the best approach to use when solving this problem. To begin, traverse both strings from either end. If both of the characters are the same, then move to the next iteration; else, compute the minimum cost for all three processes (i.e., insert, remove, and replace) and choose the option with the lowest cost.

Remember, instead of computing the edit distance for the same values in recursive calls, use memoization to store the results of subproblems.

Implementation

strA = "skip";
strB = "skid";

indexA = 0;
indexB = 0;

if (strA[indexA] == strB[indexB] {
  return editDist(strA, strB, indexA + 1, indexB + 1);
}
// minimum cost among three process.
return min(
  1 + editDist(strA, strB, indexA, indexB + 1)     // insertion
  1 + editDist(strA, strB, indexA + 1, indexB)     // removal
  2 + editDist(strA, strB, indexA + 1, indexB + 1) // replacement
)