Lesson 278
Edit Distance
Transform · DP Grid · Min Cost
1:00How to compute the minimum number of single-character edits (insert, delete, substitute) needed to transform one string into another, using a classic O(m × n) dynamic programming table.
By the end, you can
- Define edit distance and name the three allowed operations and their costs.
- Fill a DP table by hand for short strings, applying the match and mismatch recurrences correctly.
- State the base-case values and explain why `dp[i][0] = i` and `dp[0][j] = j`.
- Distinguish the match case (copy diagonal, no cost) from the mismatch case (1 + min of three neighbours).
- Trace back through the completed table to identify which edits were made.
- State the time and space complexity of the algorithm and explain the space-optimisation trade-off.
- Contrast Levenshtein, Hamming, LCS-based edit, and Damerau–Levenshtein distances.
- Give real-world examples of where edit distance is applied (spell-check, DNA alignment, fuzzy search).
Up next in String Algorithms, Advanced DP & Competitive Techniques
