Edit Distance

Leetcode Problem 72: Edit Distance

Problem Summary

Given two strings word1 and word2, return the minimum number of operations needed to convert the first into the second. The permitted operations are inserting a character, deleting a character, and replacing a character, each counting as one operation. Either word may be empty, and neither exceeds five hundred characters, all lowercase English letters.

The state is the pair of prefix lengths, and each of the three operations maps onto one neighbour of the cell. Replacing consumes a character from both words and reads the diagonal, deleting consumes a character of the first word and reads the cell above, inserting consumes a character of the second word and reads the cell on the left. When the two last characters already agree, nothing needs to be paid and the value passes through from the diagonal unchanged. The base row and base column carry the real information: turning a prefix of length i into the empty string costs i deletions, and building a prefix of length j from nothing costs j insertions.

Techniques

String
Dynamic Programming

Solution

function minDistance(word1: string, word2: string): number {
    const rows = word1.length
    const columns = word2.length
    // dp[i][j] = edit distance between the first i chars of word1 and the first j chars of word2
    const dp: number[][] = Array.from({ length: rows + 1 }, () => Array(columns + 1).fill(0))

    // turning a prefix into the empty string costs one deletion per character
    for (let i = 0; i <= rows; i++) {
        dp[i][0] = i
    }

    // building a prefix from the empty string costs one insertion per character
    for (let j = 0; j <= columns; j++) {
        dp[0][j] = j
    }

    for (let i = 1; i <= rows; i++) {
        for (let j = 1; j <= columns; 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 - 1], // replace
                    dp[i][j - 1],     // insert
                    dp[i - 1][j]      // delete
                )
            }
        }
    }

    return dp[rows][columns]
};