Intermediate LevelData Structures & Algorithms
How do you compute the Edit Distance (Levenshtein Distance) between two strings?
ā Interview Prompt: Solve Edit Distance (minimum insert, delete, replace operations) using 2D DP in O(MN) time.
Edit Distance = minimum operations (insert, delete, replace) to transform string $s1$ into $s2$.
Recurrence:
dp[i][j] = edit distance between s1[0..i-1] and s2[0..j-1].
```
if s1[i-1] === s2[j-1]: dp[i][j] = dp[i-1][j-1] (no op needed)
else: dp[i][j] = 1 + min(
dp[i-1][j], // delete from s1
dp[i][j-1], // insert into s1
dp[i-1][j-1] // replace
)
```
ā¢
Time: $O(M \times N)$, Space: $O(M \times N)$ (reducible to $O(\min(M,N))$).
Code Implementation Example
typescript
function minDistance(s1: string, s2: string): number {
const m = s1.length, n = s2.length;
const dp: number[][] = Array.from({ length: m + 1 },
(_, i) => Array.from({ length: n + 1 }, (_, j) => i || j));
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
dp[i][j] = s1[i - 1] === s2[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[m][n];
}
console.log(minDistance("horse", "ros")); // 3š”Edit Distance 2D DP ā O(MN) time with insert, delete, replace operations.
šÆ Interview Key Takeaway
Edit Distance underlies spell checkers, DNA alignment, and diff tools (git diff). The 3-way min recurrence (insert, delete, replace) is the key insight.
#DSA#Edit Distance#Dynamic Programming#Strings#Intermediate
Back to all Data Structures & Algorithms Questionsā