Edit Distance - Video Solutions

Problem Overview: Given two strings word1 and word2, compute the minimum number of operations required to convert one into the other. Allowed operations are insert, delete, and replace a character. The task is essentially measuring how different the two strings are using the fewest edits.

Approach 1: Recursive with Memoization (O(m*n) time, O(m*n) space)

This approach models the problem directly with recursion. At any index i in word1 and j in word2, you compare characters and decide which operation to apply. If the characters match, move both pointers forward with no cost. Otherwise try three choices: insert (advance j), delete (advance i), or replace (advance both). Each recursive call returns the minimum cost from that state.

Without caching, the recursion explores the same subproblems repeatedly, leading to exponential time. Memoization stores results for each (i, j) pair so every state is computed once. The number of states is m * n, where m and n are string lengths. This technique demonstrates the optimal substructure clearly and is a natural application of recursion combined with caching.

Approach 2: Dynamic Programming (Tabulation) (O(m*n) time, O(m*n) space)

The dynamic programming solution converts the recursive idea into a bottom-up table. Create a 2D DP array where dp[i][j] represents the minimum edits needed to convert the first i characters of word1 into the first j characters of word2. Initialize the first row and column because converting to or from an empty string requires only insertions or deletions.

For each cell, compare the current characters from the two strings. If they match, copy the value from dp[i-1][j-1]. If they differ, compute the minimum of three operations: insert (dp[i][j-1]), delete (dp[i-1][j]), or replace (dp[i-1][j-1]). Add one to represent the operation cost. Iterating through the matrix fills all subproblems efficiently.

This is the classic edit distance DP formulation and commonly appears when working with string transformation problems and dynamic programming. The DP table guarantees each subproblem is solved exactly once, producing an optimal solution in quadratic time.

Recommended for interviews: Interviewers typically expect the dynamic programming solution. Starting with the recursive idea shows you understand the decision process behind each edit operation. Converting it into a DP table demonstrates that you can optimize overlapping subproblems and reason about state transitions—skills that are core to dynamic programming interviews.