14.6 Edit distance problem¶

Edit distance, also called Levenshtein distance, is the minimum number of edits needed to transform one string into another. It is commonly used in information retrieval and natural language processing to measure similarity between sequences.

Question

Given two strings \(s\) and \(t\), return the minimum number of edits needed to transform \(s\) into \(t\).

Three edits are allowed: insert a character, delete a character, or replace a character with any other character.

As shown in Figure 14-27, transforming kitten into sitting takes 3 edits: 2 replacements and 1 insertion. Transforming hello into algo also takes 3 edits: 2 replacements and 1 deletion.

Examples of edit distance

Figure 14-27 Examples of edit distance

Edit distance fits naturally into a decision tree model. Strings are nodes, and each decision (an edit) is an edge.

As shown in Figure 14-28, without restrictions on the edits, each node can have many outgoing edges, one for each possible operation. Thus, many paths can transform hello into algo.

From the decision tree perspective, the goal is to find the shortest path between nodes hello and algo.

Edit distance as a decision tree

Figure 14-28 Edit distance as a decision tree

1. Dynamic programming approach¶

Step 1: Identify each decision, define the state, and establish the \(dp\) table

Each decision applies one edit to string \(s\).

We want each edit to reduce the problem's size so that we can form subproblems. Let the lengths of \(s\) and \(t\) be \(n\) and \(m\). First consider their last characters, \(s[n-1]\) and \(t[m-1]\).

If \(s[n-1]\) and \(t[m-1]\) match, skip them and consider \(s[n-2]\) and \(t[m-2]\).
If \(s[n-1]\) and \(t[m-1]\) differ, apply an edit to \(s\) (insertion, deletion, or replacement) to match the endings, allowing us to move on to a smaller problem.

Each decision (edit) in \(s\) changes the characters still to be matched in \(s\) and \(t\). The state therefore specifies the \(i\)-th and \(j\)-th characters currently under consideration in \(s\) and \(t\), denoted by \([i, j]\).

State \([i, j]\) represents the subproblem of finding the minimum number of edits needed to transform the first \(i\) characters of \(s\) into the first \(j\) characters of \(t\).

This gives a two-dimensional \(dp\) table of size \((n+1) \times (m+1)\).

Step 2: Identify optimal substructure and derive the state transition equation

For subproblem \(dp[i, j]\), the final characters are \(s[i-1]\) and \(t[j-1]\). The three possible edits give the cases shown in Figure 14-29.

Insert \(t[j-1]\) after \(s[i-1]\), leaving subproblem \(dp[i, j-1]\).
Delete \(s[i-1]\), leaving subproblem \(dp[i-1, j]\).
Replace \(s[i-1]\) with \(t[j-1]\), leaving subproblem \(dp[i-1, j-1]\).

State transitions for edit distance

Figure 14-29 State transitions for edit distance

The optimal substructure follows: the minimum edit count \(dp[i, j]\) is the smallest of \(dp[i, j-1]\), \(dp[i-1, j]\), and \(dp[i-1, j-1]\), plus \(1\) for the current edit. The state transition equation is:

\[ dp[i, j] = \min(dp[i, j-1], dp[i-1, j], dp[i-1, j-1]) + 1 \]

When \(s[i-1]\) and \(t[j-1]\) match, no edit is needed for the current characters, and the state transition equation becomes:

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

Step 3: Determine the boundary conditions and evaluation order

If both strings are empty, \(0\) edits are needed, so \(dp[0, 0] = 0\). If \(s\) is empty but \(t\) is not, the minimum edit count is the length of \(t\), giving the first row \(dp[0, j] = j\). If \(s\) is nonempty but \(t\) is empty, the count is the length of \(s\), giving the first column \(dp[i, 0] = i\).

The solution \(dp[i, j]\) depends on entries to its left, above, and upper left, so two nested loops can traverse the \(dp\) table in increasing index order.

2. Code implementation¶

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

edit_distance.py

def edit_distance_dp(s: str, t: str) -> int:
    """Edit distance: dynamic programming"""
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    # State transitions: first row and first column
    for i in range(1, n + 1):
        dp[i][0] = i
    for j in range(1, m + 1):
        dp[0][j] = j
    # State transitions: remaining rows and columns
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s[i - 1] == t[j - 1]:
                # If the two characters are equal, skip both of them
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
    return dp[n][m]

edit_distance.cpp

/* Edit distance: dynamic programming */
int editDistanceDP(string s, string t) {
    int n = s.length(), m = t.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    // State transitions: first row and first column
    for (int i = 1; i <= n; i++) {
        dp[i][0] = i;
    }
    for (int j = 1; j <= m; j++) {
        dp[0][j] = j;
    }
    // State transitions: remaining rows and columns
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                // If the two characters are equal, skip both of them
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
                dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[n][m];
}

edit_distance.java

/* Edit distance: dynamic programming */
int editDistanceDP(String s, String t) {
    int n = s.length(), m = t.length();
    int[][] dp = new int[n + 1][m + 1];
    // State transitions: first row and first column
    for (int i = 1; i <= n; i++) {
        dp[i][0] = i;
    }
    for (int j = 1; j <= m; j++) {
        dp[0][j] = j;
    }
    // State transitions: remaining rows and columns
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                // If the two characters are equal, skip both of them
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
                dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[n][m];
}

edit_distance.cs

/* Edit distance: dynamic programming */
int EditDistanceDP(string s, string t) {
    int n = s.Length, m = t.Length;
    int[,] dp = new int[n + 1, m + 1];
    // State transitions: first row and first column
    for (int i = 1; i <= n; i++) {
        dp[i, 0] = i;
    }
    for (int j = 1; j <= m; j++) {
        dp[0, j] = j;
    }
    // State transitions: remaining rows and columns
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                // If the two characters are equal, skip both of them
                dp[i, j] = dp[i - 1, j - 1];
            } else {
                // Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
                dp[i, j] = Math.Min(Math.Min(dp[i, j - 1], dp[i - 1, j]), dp[i - 1, j - 1]) + 1;
            }
        }
    }
    return dp[n, m];
}

edit_distance.go

/* Edit distance: dynamic programming */
func editDistanceDP(s string, t string) int {
    n := len(s)
    m := len(t)
    dp := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, m+1)
    }
    // State transitions: first row and first column
    for i := 1; i <= n; i++ {
        dp[i][0] = i
    }
    for j := 1; j <= m; j++ {
        dp[0][j] = j
    }
    // State transitions: remaining rows and columns
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if s[i-1] == t[j-1] {
                // If the two bytes are equal, skip both (each byte is one character for ASCII input)
                dp[i][j] = dp[i-1][j-1]
            } else {
                // Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
                dp[i][j] = MinInt(MinInt(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1
            }
        }
    }
    return dp[n][m]
}

edit_distance.swift

/* Edit distance: dynamic programming */
func editDistanceDP(s: String, t: String) -> Int {
    let n = s.utf8CString.count
    let m = t.utf8CString.count
    var dp = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1)
    // State transitions: first row and first column
    for i in 1 ... n {
        dp[i][0] = i
    }
    for j in 1 ... m {
        dp[0][j] = j
    }
    // State transitions: remaining rows and columns
    for i in 1 ... n {
        for j in 1 ... m {
            if s.utf8CString[i - 1] == t.utf8CString[j - 1] {
                // If the two current UTF-8 bytes match, skip both
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                // Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
                dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1
            }
        }
    }
    return dp[n][m]
}

edit_distance.js

/* Edit distance: dynamic programming */
function editDistanceDP(s, t) {
    const n = s.length,
        m = t.length;
    const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
    // State transitions: first row and first column
    for (let i = 1; i <= n; i++) {
        dp[i][0] = i;
    }
    for (let j = 1; j <= m; j++) {
        dp[0][j] = j;
    }
    // State transitions: remaining rows and columns
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (s.charAt(i - 1) === t.charAt(j - 1)) {
                // If the two characters are equal, skip both of them
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
                dp[i][j] =
                    Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[n][m];
}

edit_distance.ts

/* Edit distance: dynamic programming */
function editDistanceDP(s: string, t: string): number {
    const n = s.length,
        m = t.length;
    const dp = Array.from({ length: n + 1 }, () =>
        Array.from({ length: m + 1 }, () => 0)
    );
    // State transitions: first row and first column
    for (let i = 1; i <= n; i++) {
        dp[i][0] = i;
    }
    for (let j = 1; j <= m; j++) {
        dp[0][j] = j;
    }
    // State transitions: remaining rows and columns
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (s.charAt(i - 1) === t.charAt(j - 1)) {
                // If the two characters are equal, skip both of them
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
                dp[i][j] =
                    Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[n][m];
}

edit_distance.dart

/* Edit distance: dynamic programming */
int editDistanceDP(String s, String t) {
  int n = s.length, m = t.length;
  List<List<int>> dp = List.generate(n + 1, (_) => List.filled(m + 1, 0));
  // State transitions: first row and first column
  for (int i = 1; i <= n; i++) {
    dp[i][0] = i;
  }
  for (int j = 1; j <= m; j++) {
    dp[0][j] = j;
  }
  // State transitions: remaining rows and columns
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (s[i - 1] == t[j - 1]) {
        // If the two characters are equal, skip both of them
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        // Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
        dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
      }
    }
  }
  return dp[n][m];
}

edit_distance.rs

/* Edit distance: dynamic programming */
fn edit_distance_dp(s: &str, t: &str) -> i32 {
    let (n, m) = (s.len(), t.len());
    let mut dp = vec![vec![0; m + 1]; n + 1];
    // State transitions: first row and first column
    for i in 1..=n {
        dp[i][0] = i as i32;
    }
    for j in 1..m {
        dp[0][j] = j as i32;
    }
    // State transitions: remaining rows and columns
    for i in 1..=n {
        for j in 1..=m {
            if s.chars().nth(i - 1) == t.chars().nth(j - 1) {
                // If the two characters are equal, skip both of them
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
                dp[i][j] =
                    std::cmp::min(std::cmp::min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    dp[n][m]
}

edit_distance.c

/* Edit distance: dynamic programming */
int editDistanceDP(char *s, char *t, int n, int m) {
    int **dp = malloc((n + 1) * sizeof(int *));
    for (int i = 0; i <= n; i++) {
        dp[i] = calloc(m + 1, sizeof(int));
    }
    // State transitions: first row and first column
    for (int i = 1; i <= n; i++) {
        dp[i][0] = i;
    }
    for (int j = 1; j <= m; j++) {
        dp[0][j] = j;
    }
    // State transitions: remaining rows and columns
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                // If the two characters are equal, skip both of them
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
                dp[i][j] = myMin(myMin(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    int res = dp[n][m];
    // Free memory
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    return res;
}

edit_distance.kt

/* Edit distance: dynamic programming */
fun editDistanceDP(s: String, t: String): Int {
    val n = s.length
    val m = t.length
    val dp = Array(n + 1) { IntArray(m + 1) }
    // State transitions: first row and first column
    for (i in 1..n) {
        dp[i][0] = i
    }
    for (j in 1..m) {
        dp[0][j] = j
    }
    // State transitions: remaining rows and columns
    for (i in 1..n) {
        for (j in 1..m) {
            if (s[i - 1] == t[j - 1]) {
                // If the two characters are equal, skip both of them
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                // Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
                dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1
            }
        }
    }
    return dp[n][m]
}

edit_distance.rb

### Edit distance: dynamic programming ###
def edit_distance_dp(s, t)
  n, m = s.length, t.length
  dp = Array.new(n + 1) { Array.new(m + 1, 0) }
  # State transitions: first row and first column
  (1...(n + 1)).each { |i| dp[i][0] = i }
  (1...(m + 1)).each { |j| dp[0][j] = j }
  # State transitions: remaining rows and columns
  for i in 1...(n + 1)
    for j in 1...(m +1)
      if s[i - 1] == t[j - 1]
        # If the two characters are equal, skip both of them
        dp[i][j] = dp[i - 1][j - 1]
      else
        # Minimum edits = the minimum among the insertion, deletion, and replacement subproblems + 1
        dp[i][j] = [dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]].min + 1
      end
    end
  end
  dp[n][m]
end

Visualize execution

View full screen >

As shown in Figure 14-30, the state transition process resembles that of the knapsack problem: both fill a two-dimensional grid.

Figure 14-30 Dynamic programming for edit distance

3. Space optimization¶

The state \(dp[i,j]\) depends on \(dp[i-1, j]\) above, \(dp[i, j-1]\) to the left, and \(dp[i-1, j-1]\) at the upper left. Forward iteration loses \(dp[i-1, j-1]\), while backward iteration cannot compute \(dp[i, j-1]\) in advance. Neither order alone is sufficient.

We can use a variable leftup to preserve the upper-left solution \(dp[i-1, j-1]\), leaving only the left and upper entries to consider. The situation then matches unbounded knapsack, and forward iteration works. The code is as follows: