Edit Distance is one of the most important String Dynamic Programming interview questions.

You are given two strings:

word1word2

Goal:

Find the minimum number of operations required to convert word1 into word2. 

Allowed Operations:

Insert
Delete
Replace 

Example

word1 = "horse"word2 = "ros"

Output:

3 

Explanation:

horse→ rorse (replace h with r)
→ rose (delete r)
→ ros (delete e)

Total Operations:

3 

Key Observation

If characters match:

dp[i][j] = dp[i-1][j-1] 

If characters do not match:

dp[i][j] = 1 + min(insert, delete, replace) 

This forms the DP recurrence.

Approach 1 : Memoization

Explanation

Use recursion with caching.

Steps:

1. Compare characters.
2. If equal, move diagonally.
3. Otherwise try insert, delete, replace.
4. Store computed answers.
5. Reuse results.

Approach 2 : Tabulation

Explanation

Build a DP table from smaller prefixes.

Base Cases:

dp[i][0] = i
dp[0][j] = j 

Meaning:

Convert string to empty string using deletions.
Convert empty string to string using insertions. 

Transition:

If characters match:
dp[i][j] = dp[i-1][j-1]

Else:
dp[i][j] = 1 + min(insert, delete, replace) 

Dry Run

Input:

word1 = "horse"
word2 = "ros" 

Final DP Result:

Answer = 3 

Operations:

Replace h → r
Delete r
Delete e 

Approach 3 : Space Optimized DP

Explanation

Instead of storing the entire matrix:

 m × n

Store only:

Previous Row
Current Row 

This reduces memory usage.

Practice

MemoizationTime Complexity: O(m × n)
Space Complexity: O(m × n)

Tabulation
Time Complexity: O(m × n)
Space Complexity: O(m × n)

Space Optimized DP
Time Complexity: O(m × n)
Space Complexity: O(n)

If characters match: Move diagonally.If not:
Try insert, delete, and replace.
Take the minimum operation count.