58. Edit Distance

Given two strings s1 and s2, find the minimum number of operations (insert, delete, or replace a single character) needed to convert s1 into s2.

Input: Two lines: the first contains s1, the second contains s2. Output: Print a single integer - the minimum edit distance between s1 and s2.

0 <= |s1|, |s2| <= 1000

The base cases (dp[0][j] = j, dp[i][0] = i) represent 'transforming an empty string into a string of length j needs j insertions' (and vice versa for deletions) - these anchor the whole table and are easy to get wrong if rushed.

Find the minimum number of single-character insertions, deletions, or replacements needed to transform one string into another. Brute force: Try every possible sequence of insert/delete/replace operations recursively - this branches exponentially without memoization, since the same (i,j) sub-alignment gets recomputed repeatedly across different edit orderings. Optimised: The DP table captures the reusable insight that the edit distance between two prefixes only depends on the edit distances of slightly shorter prefixes (three specific smaller sub-problems) - filling the table bottom-up computes every needed value exactly once, turning exponential search into a table of (|s1|+1)*(|s2|+1) cells.

Recursively compute the edit distance between s1 and s2 by trying all three operations at every mismatched character: insert, delete, or replace, recursing on the corresponding smaller subproblem each time, and taking the minimum plus a base case when either string is exhausted. This directly implements the definition of edit distance but recomputes the exact same (i, j) subproblems exponentially many times. Time: O(3^max(m,n)) Space: O(max(m,n)) recursion depth

Build the DP table iteratively from smaller prefixes upward instead of recursing top-down, where dp[i][j] is the edit distance between the first i characters of s1 and first j characters of s2, computed from dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]. Since each row only depends on the previous row, only two rows (or one row updated in place) need to be kept at any time, cutting the space from O(m*n) to O(min(m,n)) while keeping the same O(m*n) time. Time: O(m*n) Space: O(min(m,n))

Keep the same recursive structure as the brute force but cache the result for each (i, j) pair of remaining prefixes in a memo table, so any subproblem is solved only once. Since there are only O(m*n) distinct (i, j) states and each is solved in O(1) work given its children's cached answers, this collapses the exponential blowup into polynomial time. Time: O(m*n) Space: O(m*n)

1. Build a 2D DP table where dp[i][j] means 'the edit distance between the first i characters of s1 and the first j characters of s2'. 2. If the current characters match, no edit is needed here: dp[i][j] = dp[i-1][j-1]. 3. If they don't match, take the best of three possible single-edit choices (insert, delete, replace) and add 1: dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]).

Time: O(|s1| * |s2|) - filling the entire DP table, one cell per pair of prefix lengths. Space: O(|s1| * |s2|) for the full table (reducible to O(min(|s1|,|s2|)) with a rolling array, since each row only depends on the row directly above it).

Test with either or both strings empty (0 is an allowed length), s1 equal to s2 (distance 0), strings that share no characters at all, and both strings at length 1000 to check performance.

This is one of the most fundamental DP problems in computer science, underlying real spell-checkers, DNA sequence alignment, and diff tools - be ready to derive the three-way recurrence (insert/delete/replace) from first principles, not just recite it.