Edit Distance
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
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];}