Edit distance

Hard

Insert, delete or replace — take the cheapest

Problem

Return the minimum insert/delete/replace operations to convert one string into another.

In simple words

Fill a grid of edit costs; each cell picks the cheapest of insert, delete, or replace.

The idea

If the characters match, nothing is needed and the cost carries diagonally. Otherwise it is one plus the cheapest of the three neighbouring states, each corresponding to one edit operation.

The trick

Diagonal = replace, left = insert, up = delete.
Base row and column are 0..n — converting to or from an empty string.
O(m·n); two rows of storage suffice.

←→stepspaceplay

∅

1/8

Optimal

timeO(n·m)spaceO(n·m)

Match extends the diagonal.

1for (let i = 1; i <= n; i++)2  for (let j = 1; j <= m; j++)3    dp[i][j] = a[i-1] === b[j-1]4      ? dp[i-1][j-1] + 15      : Math.max(dp[i-1][j], dp[i][j-1]);

Input

grid: 5 × 4

Memory

at: —
cells marked: 0

Output

LCS: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: a = "horse", b = "ros"
Output:: 3
Explanation:: 3 edits: replace h→r, remove r, remove e.

Example 2

Input:: a = "intention", b = "execution"
Output:: 5
Explanation:: 5 edits transform one into the other.

Example 3

Input:: a = "abc", b = "abc"
Output:: 0
Explanation:: Already equal → 0 edits.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.