ProgramGuru

Edit Distance Problem

Problem and examples

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.

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

Explore Edit Distance Problem - DP

Load an example or enter your own input. Use the player controls to follow each change.

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.

  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].

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int editDistance(const string &word1, const string &word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    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]});
            }
        }
    }
    return dp[m][n];
}

int main() {
    cout << "Edit Distance between 'kitten' and 'sitting': " << editDistance("kitten", "sitting") << endl;
    cout << "Edit Distance between 'horse' and 'ros': " << editDistance("horse", "ros") << endl;
    return 0;
}

Python implementation

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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])
    return dp[m][n]

if __name__ == '__main__':
    print("Edit Distance between 'kitten' and 'sitting':", edit_distance("kitten", "sitting"))
    print("Edit Distance between 'horse' and 'ros':", edit_distance("horse", "ros"))

Java implementation

public class EditDistance {
    public static int editDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        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.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                }
            }
        }
        return dp[m][n];
    }
    public static void main(String[] args) {
        System.out.println("Edit Distance between 'kitten' and 'sitting': " + editDistance("kitten", "sitting"));
        System.out.println("Edit Distance between 'horse' and 'ros': " + editDistance("horse", "ros"));
    }
}

JavaScript implementation

function editDistance(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] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
            }
        }
    }
    return dp[m][n];
}

console.log("Edit Distance between 'kitten' and 'sitting':", editDistance("kitten", "sitting"));
console.log("Edit Distance between 'horse' and 'ros':", editDistance("horse", "ros"));

Go implementation

package main

import (
    "fmt"
)

func min(a, b, c int) int {
    if a < b {
        if a < c {
            return a
        }
        return c
    }
    if b < c {
        return b
    }
    return c
}

func editDistance(word1, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    for i := 1; i <= m; i++ {
        for 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])
            }
        }
    }
    return dp[m][n]
}

func main() {
    fmt.Println("Edit Distance between 'kitten' and 'sitting':", editDistance("kitten", "sitting"))
    fmt.Println("Edit Distance between 'horse' and 'ros':", editDistance("horse", "ros"))
}

Rust implementation

fn edit_distance(word1: &str, word2: &str) -> usize {
    let m = word1.len();
    let n = word2.len();
    let w1: Vec<char> = word1.chars().collect();
    let w2: Vec<char> = word2.chars().collect();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 0..=m { dp[i][0] = i; }
    for j in 0..=n { dp[0][j] = j; }

    for i in 1..=m {
        for j in 1..=n {
            if w1[i - 1] == w2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + std::cmp::min(dp[i - 1][j], std::cmp::min(dp[i][j - 1], dp[i - 1][j - 1]));
            }
        }
    }
    dp[m][n]
}

fn main() {
    println!("Edit Distance between 'kitten' and 'sitting': {}", edit_distance("kitten", "sitting"));
    println!("Edit Distance between 'horse' and 'ros': {}", edit_distance("horse", "ros"));
}

Kotlin implementation

fun editDistance(word1: String, word2: String): Int {
    val m = word1.length
    val n = word2.length
    val dp = Array(m + 1) { IntArray(n + 1) }
    for (i in 0..m) dp[i][0] = i
    for (j in 0..n) dp[0][j] = j
    for (i in 1..m) {
        for (j in 1..n) {
            dp[i][j] = if (word1[i - 1] == word2[j - 1]) {
                dp[i - 1][j - 1]
            } else {
                1 + minOf(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
            }
        }
    }
    return dp[m][n]
}

fun main() {
    println("Edit Distance between 'kitten' and 'sitting': ${editDistance("kitten", "sitting")}")
    println("Edit Distance between 'horse' and 'ros': ${editDistance("horse", "ros")}")
}

Swift implementation

func editDistance(_ word1: String, _ word2: String) -> Int {
    let m = word1.count, n = word2.count
    let w1 = Array(word1), w2 = Array(word2)
    var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
    for i in 0...m { dp[i][0] = i }
    for j in 0...n { dp[0][j] = j }
    for i in 1...m {
        for j in 1...n {
            if w1[i - 1] == w2[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])
            }
        }
    }
    return dp[m][n]
}

print("Edit Distance between 'kitten' and 'sitting':", editDistance("kitten", "sitting"))
print("Edit Distance between 'horse' and 'ros':", editDistance("horse", "ros"))

TypeScript implementation

function editDistance(word1: string, word2: string): number {
    const m = word1.length, n = word2.length;
    const dp: number[][] = 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] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
            }
        }
    }
    return dp[m][n];
}

console.log("Edit Distance between 'kitten' and 'sitting':", editDistance("kitten", "sitting"));
console.log("Edit Distance between 'horse' and 'ros':", editDistance("horse", "ros"));