01. Edit Distance (Levenshtein Distance)

Difficulty:HardPattern:2D Dynamic ProgrammingTime:O(m * n)Space:O(m * n)

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2 using insertions, deletions, or substitutions.

How It Works & Algorithmic Design

Solves using 2D Dynamic Programming Grid Matching:

DP State: Define dp[i][j] as the minimum edit distance between word1[0...i-1] and word2[0...j-1].
Base Cases: dp[i][0] = i (deleting all characters from word1) and dp[0][j] = j (inserting all characters into word1).
State Transitions:
- If word1[i-1] === word2[j-1], no operation is needed: dp[i][j] = dp[i-1][j-1].
- Otherwise, take the minimum of 3 operations plus 1:
  - Insert: dp[i][j-1] + 1
  - Delete: dp[i-1][j] + 1
  - Replace: dp[i-1][j-1] + 1

Why This Approach Works Best

Computes exact minimum edit distance in $O(m \times n)$ time and $O(m \times n)$ space, which can be space-optimized to $O(\min(m, n))$ using rolling arrays.

Example Walkthrough

Input: word1 = "horse", word2 = "ros"

Target conversion.

Operations Trace: horse -> rorse (replace 'h' with 'r') -> rose (remove 'r') -> ros (remove 'e')

3 operations required.

Output: 3

Minimum operations.

Answer: Edit Distance 2D DP implementation

function minDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
      }
    }
  }
  return dp[m][n];
}

💡 Build dynamic programming table evaluating insert, delete, and replace operational paths.

Key Takeaways

Minimizes structural distance across two sequences.
Sub-problem operations: Insert (left cell), Delete (top cell), Replace (diagonal cell).
Time complexity $O(m \times n)$.