Edit Distance

Median of Two Sorted Arrays

Trapping Rain Water

Measure the minimum insertions, deletions, and replacements between two strings.

Return the minimum number of single-character insertions, deletions, or replacements needed to transform `word1` into `word2`.

**Input / output**
- Input: `word1: string`, `word2: string`
- Output: integer edit distance

**Examples**
1. `"horse"` to `"ros"` requires `3` edits.
2. An empty string to `"abc"` requires `3` insertions.

**Constraints**
- `0 <= word1.length, word2.length <= 500`
- Strings contain lowercase English letters

**Follow-up**
How can you reduce the dynamic-programming memory from quadratic to linear?

- Let `dp[i][j]` be the minimum edits needed to convert the first `i` characters of `word1` into the first `j` characters of `word2`.
- Empty prefixes give the base cases: converting to or from an empty string requires only insertions or deletions.
- The final answer is the value for the full lengths of both words.

Define the Subproblem

- If the current characters match, no new edit is needed and we reuse the diagonal subproblem.
- Otherwise, try the cheapest of insert, delete, or replace.
- Each operation costs one edit plus the best smaller subproblem.

Choose Between the Three Operations

- The recurrence only needs the previous row and the current row.
- Store distances for converting the processed prefix of `word1` to every prefix of `word2`.
- For each character in `word1`, build a fresh `current` row from `previous`.

Optimize Space with One Row

- `current[j - 1]` represents insertion, because the target prefix is one character shorter.
- `previous[j]` represents deletion, because the source prefix is one character shorter.
- `previous[j - 1]` represents replacement or a character match.

Fill Rows Left to Right

- This dynamic programming solution handles empty strings through the initialized base row and first column.
- It keeps only one previous row, so memory is linear in the length of `word2`.
- Time complexity is O(mn), and extra space complexity is O(n).