Edit Distance Problem Using Dynamic Programming

Strings

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

The Edit Distance problem asks: Given two strings word1 and word2, what is the minimum number of operations required to convert word1 into word2?

  • Allowed operations are:
    • Insert a character
    • Delete a character
    • Replace a character
  • Each operation counts as 1 step.

The goal is to find the minimum number of such operations needed to make the two strings equal.

Examples❯

Word 1 Word 2 Edit Distance Description
"horse" "ros" 3 Replace 'h' → 'r', remove 'r', remove 'e'
"intention" "execution" 5 Requires multiple inserts, deletes, and replacements
"abc" "abc" 0 Both strings are already equal
"abc" "def" 3 All characters need to be replaced
"abcd" "abc" 1 Only one deletion is needed
"abc" "abcd" 1 Only one insertion is needed
"" "abc" 3 Empty word1, need 3 insertions
"abc" "" 3 Empty word2, need 3 deletions
"" "" 0 Both strings are empty, no operations needed

Solution❯

Understanding the Problem

The Edit Distance problem asks us to find the minimum number of operations required to convert one string into another. The allowed operations are:

  • Insert a character
  • Delete a character
  • Replace a character

Each operation costs 1 unit, and our goal is to convert word1 to word2 in the fewest steps possible.

Step-by-Step Solution with Example

Step 1: Understand the goal through an example

Suppose word1 = "horse" and word2 = "ros". We need to transform "horse" into "ros" using the fewest insertions, deletions, or replacements.

Step 2: Break down the transformations

Let's compare characters step by step:

  • 'h' in "horse" ≠ 'r' in "ros" → Replace 'h' with 'r' (cost: 1)
  • 'o' = 'o' → No operation (cost: 0)
  • 'r' = 's'? No → Replace 'r' with 's' or delete 'r' and insert 's'
  • Continue comparing and choosing the minimal cost operation at each step

Step 3: Use Dynamic Programming

We define dp[i][j] as the edit distance between the first i characters of word1 and the first j characters of word2.

  • If i == 0, we need j insertions
  • If j == 0, we need i deletions
  • If word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1]
  • Else, dp[i][j] = 1 + min(
    • dp[i-1][j] // delete
    • dp[i][j-1] // insert
    • dp[i-1][j-1] // replace
    )

Step 4: Build the DP table

We start with an empty 2D table of size (m+1) x (n+1) where m = length of word1 and n = length of word2. Fill in the base cases for empty strings, then fill the rest based on the rules above.

Step 5: Get the result

The final answer will be in dp[m][n], which tells us the edit distance for the full lengths of both strings.

Edge Cases

  • Both strings are empty: The edit distance is 0
  • One string is empty: The edit distance is the length of the other string (all insertions or deletions)
  • Both strings are the same: No operations needed; distance is 0
  • Case sensitivity: 'A' ≠ 'a'; so replacement is needed if case doesn't match

Finally

This problem teaches a foundational dynamic programming technique. By comparing subproblems and building up the solution in a 2D table, we avoid recomputation and ensure the optimal number of steps.

Always begin by breaking the problem into manageable steps, test your solution with examples, and handle edge cases thoughtfully to ensure correctness.

Algorithm Steps❯

  1. Let word1 and word2 be the input strings, with lengths m and n respectively.
  2. Create a 2D table dp of dimensions (m+1) x (n+1), where dp[i][j] represents the edit distance between the first i characters of word1 and the first j characters of word2.
  3. Initialize the first column: for each i from 0 to m, set dp[i][0] = i (representing i deletions).
  4. Initialize the first row: for each j from 0 to n, set dp[0][j] = j (representing j insertions).
  5. For each i from 1 to m and for each j from 1 to n:
    1. If word1[i-1] equals word2[j-1], then set dp[i][j] = dp[i-1][j-1].
    2. Otherwise, set dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
  6. The edit distance is dp[m][n].

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int min(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int editDistance(const char *word1, const char *word2) {
    int m = strlen(word1), n = strlen(word2);
    int **dp = malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        dp[i] = malloc((n + 1) * sizeof(int));
    }
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
            }
        }
    }
    int distance = dp[m][n];
    for (int i = 0; i <= m; i++) free(dp[i]);
    free(dp);
    return distance;
}

int main() {
    printf("Edit Distance between 'kitten' and 'sitting': %d\n", editDistance("kitten", "sitting"));
    printf("Edit Distance between 'horse' and 'ros': %d\n", editDistance("horse", "ros"));
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...