Edit Distance

Find the fewest insert, delete, or replace steps needed to change one string into another.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Edit Distance: Fill prefix edit costs: matches copy the diagonal; mismatches add one to min(insert, delete, replace).

Input and goalFind the fewest insert, delete, or replace steps needed to change one string into another.

Initialize empty-prefix costsFor first = "cat" and second = "cut", row 0 is insert counts 0..3 and column 0 is delete counts 0..3.

0base1231???2???3???

columnsempty, c, u, trowAxisempty, c, a, t

Recognize it

Use it when transforming one sequence prefix into another permits local insert, delete, and replace operations and asks for the minimum total operation count.

Keep true

After current[j] is appended, it is the minimum edits from the processed first prefix to second[:j]; its left, up, and diagonal dependencies are already final.

Reuse it

For minimum transformation problems, define prefix states and map each allowed operation to the predecessor state it leaves behind; then add operation cost to the best predecessor.

Pattern: Grid DP stored as two rows.

State: The fewest edits between two prefixes.

Simple idea: Equal characters need no new edit. Different characters try insert, delete, and replace, then add one to the smallest earlier answer.

def edit_distance(first: str, second: str) -> int:
   previous = list(range(len(second) + 1))

   for first_index, first_char in enumerate(first, 1):
      current = [first_index]
      for second_index, second_char in enumerate(second, 1):
         if first_char == second_char:
            current.append(previous[second_index - 1])
         else:
            insert = current[-1]
            delete = previous[second_index]
            replace = previous[second_index - 1]
            current.append(1 + min(insert, delete, replace))
      previous = current

   return previous[-1]

Cost: $O(mn)$ time and $O(n)$ space.