Log inSign up
hardLeetCodeNot Started

Edit Distance

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word: 1. Insert a character 2. Delete a character 3. Replace a character

### Example 1 - Input: word1 = "horse", word2 = "ros" - Output: 3 - Explanation: - horse -> rorse (replace h with r) - rorse -> rose (remove r) - rose -> ros (remove e)

### Example 2 - Input: word1 = "intention", word2 = "execution" - Output: 5 - Explanation: - intention -> inention (remove t) - inention -> enention (replace i with e) - enention -> exention (replace n with x) - exention -> exection (replace n with c) - exection -> execution (insert u)

Constraints:

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Derive the classic Levenshtein distance 3-operation recurrence.
  • Establish proper base cases for non-empty vs empty string transformations.
  • Optimize matrix storage from O(m * n) to O(n).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Transforming one string into another with insert, delete, replace operations.
  • Minimizing total edit operations (Levenshtein distance).

Algorithmic Decision Tree:

  • If characters equal -> diagonal value without cost.
  • If characters differ -> 1 + min(left, up, diagonal).

Connected Patterns:

Longest Common SubsequenceDelete Operation for Two StringsOne Edit Distance

1. Recursive Exhaustive Search

Intuition

Recursively evaluate all 3 edit operations at each mismatched character.

Algorithm

  1. Define dfs(i, j).
  2. If i == 0, return j (must insert j characters).
  3. If j == 0, return i (must delete i characters).
  4. If word1[i-1] == word2[j-1], return dfs(i-1, j-1).
  5. Return 1 + min({dfs(i-1, j), dfs(i, j-1), dfs(i-1, j-1)}).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7int dfs(int i, int j, const string& w1, const string& w2) {
8 if (i == 0) return j;
9 if (j == 0) return i;
10
11 if (w1[i - 1] == w2[j - 1]) {
12 return dfs(i - 1, j - 1, w1, w2);
13 }
14 int del = dfs(i - 1, j, w1, w2);
15 int ins = dfs(i, j - 1, w1, w2);
16 int rep = dfs(i - 1, j - 1, w1, w2);
17 return 1 + min({del, ins, rep});
18}
19
20int minDistanceRec(string word1, string word2) {
21 return dfs(word1.length(), word2.length(), word1, word2);
22}
23
24int main() {
25 string word1 = "horse", word2 = "ros";
26 cout << "Edit Distance (Recursive): " << minDistanceRec(word1, word2) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(3^(m + n))
  • Space complexity: O(m + n) call stack

2. 2D Dynamic Programming Tabulation

Intuition

Build matrix dp[m + 1][n + 1] storing edit distances for all prefix pairs.

Algorithm

  1. Let m = word1.length, n = word2.length.
  2. Initialize dp[m + 1][n + 1].
  3. For i = 0 to m: dp[i][0] = i.
  4. For j = 0 to n: dp[0][j] = j.
  5. For i = 1 to m:
  6. For j = 1 to n:
  7. If word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1]
  8. Else: dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]})
  9. Return dp[m][n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8int minDistance2D(string word1, string word2) {
9 int m = word1.length(), n = word2.length();
10 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
11
12 for (int i = 0; i <= m; i++) dp[i][0] = i;
13 for (int j = 0; j <= n; j++) dp[0][j] = j;
14
15 for (int i = 1; i <= m; i++) {
16 for (int j = 1; j <= n; j++) {
17 if (word1[i - 1] == word2[j - 1]) {
18 dp[i][j] = dp[i - 1][j - 1];
19 } else {
20 dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
21 }
22 }
23 }
24 return dp[m][n];
25}
26
27int main() {
28 string word1 = "horse", word2 = "ros";
29 cout << "Edit Distance (2D DP): " << minDistance2D(word1, word2) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

3. 1D Array Space-Optimized Tabulation

Intuition

Maintain a single array dp of size n + 1. Use a scalar prevDiagonal to track dp[i-1][j-1].

Algorithm

  1. Let m = word1.length, n = word2.length.
  2. Initialize dp of size n + 1 with dp[j] = j.
  3. For i = 1 to m:
  4. prev = dp[0]
  5. dp[0] = i
  6. For j = 1 to n:
  7. temp = dp[j]
  8. If word1[i - 1] == word2[j - 1]: dp[j] = prev
  9. Else: dp[j] = 1 + min({dp[j] (delete), dp[j - 1] (insert), prev (replace)})
  10. prev = temp
  11. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8int minDistanceOptimal(string word1, string word2) {
9 int m = word1.length(), n = word2.length();
10 vector<int> dp(n + 1);
11 for (int j = 0; j <= n; j++) dp[j] = j;
12
13 for (int i = 1; i <= m; i++) {
14 int prev = dp[0];
15 dp[0] = i;
16 for (int j = 1; j <= n; j++) {
17 int temp = dp[j];
18 if (word1[i - 1] == word2[j - 1]) {
19 dp[j] = prev;
20 } else {
21 dp[j] = 1 + min({dp[j], dp[j - 1], prev});
22 }
23 prev = temp;
24 }
25 }
26 return dp[n];
27}
28
29int main() {
30 string word1 = "horse", word2 = "ros";
31 cout << "Edit Distance (Optimal 1D DP): " << minDistanceOptimal(word1, word2) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(n) space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive SearchO(3^(m + n))O(m + n)Branching over insert, delete, replace.Redundant subproblem branches
2.2D TabulationO(m * n)O(m * n)Full matrix grid evaluation.Matrix allocation
3.1D Array Space OptimizedOptimalO(m * n)O(n)Single 1D array with prev diagonal scalar.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to initialize base row (dp[0][j] = j) and base column (dp[i][0] = i).

Pitfall 2:

Overwriting the diagonal state before reading it when using 1D space optimization.

Crucial Edge Cases to Validate:

  • Either string is empty: Edit distance is the length of the other string.
  • Both strings are empty: Output is 0.
  • Both strings are identical: Output is 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Connect Edit Distance to real-world applications: DNA sequence alignment (Needleman-Wunsch algorithm), spell checkers, and diff utilities.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.In the Edit Distance DP table, which operations correspond to the transitions from dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] respectively?

Back to DSA Sheet