Edit Distance

Medium

Problem

Given strings a and b, return the minimum number of single-character operations (insert, delete or replace) needed to turn a into b.

Example 1

Input:  a = "horse", b = "ros"
Output: 3

Replace h→r, delete r, delete e.

Also asked as: EDIT Distance · Transform One String to Another using Minimum Number of Given Operation

Test cases

Case 1

Input:    "horse", "ros"
Expected: 3

Case 2

Input:    "intention", "execution"
Expected: 5

Case 3

Input:    "", "a"
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. 2-D DP (Levenshtein)

Time O(n · m)Space O(n · m)

dp[i][j] = edits to turn a[..i] into b[..j]: 0 if chars match on the diagonal, else 1 + min(insert, delete, replace).

function editDistance(a, b) {
const n = a.length, m = b.length;
const dp = Array.from({ length: n + 1 }, (_, i) => Array(m + 1).fill(0).map((_, j) => (i === 0 ? j : j === 0 ? i : 0)));
for (let i = 1; i <= n; i++)
for (let j = 1; j <= m; j++)
dp[i][j] = a[i - 1] === b[j - 1]
? dp[i - 1][j - 1]
: 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
return dp[n][m];
}