Return the minimum number of single-character insertions, deletions and replacements to convert word1 into word2.
Before you code
dp[i][j] is the distance between the first i characters of word1 and the first j of word2. The first row and column are 0, 1, 2, …
Hints
- If the last characters match, copy the diagonal.
- Otherwise 1 + min(above, left, diagonal): delete, insert, replace.
- Then keep only two rows, and as a stretch, walk back through a full table to print the edits.
Production & complexity notes
When solving Edit distance on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Rebuilding the answer and saving memory to reinforce the underlying pattern.
What it practices
Saving memory, and reconstructing the edits, from Rebuilding the answer and saving memory.