NUHMAN.com

Introduction

LeetCode 72: Edit Distance is one of the most important dynamic programming problems, often asked in technical interviews. It involves transforming one string into another using the fewest possible operations.

This problem is also known as the Levenshtein Distance, and it's fundamental in text similarity, spell checkers, and DNA sequence alignment.

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You may perform the following operations:

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

Examples:

go

Input: word1 = "horse", word2 = "ros"
Output: 3
// Explanation:
// horse -> rorse (replace 'h' with 'r')
// rorse -> rose (remove 'r')
// rose -> ros (remove 'e')

Input: word1 = "intention", word2 = "execution"
Output: 5

Approach: Dynamic Programming

We solve this using a 2D DP table, where dp[i][j] represents the minimum number of operations to convert the first i characters of word1 into the first j characters of word2.

Recurrence Relation:

If characters match:

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

If not:

swift

dp[i][j] = 1 + min(
    dp[i-1][j],   // delete
    dp[i][j-1],   // insert
    dp[i-1][j-1]  // replace
)

Go Implementation

go

func minDistance(word1 string, 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],   // delete
                    dp[i][j-1],   // insert
                    dp[i-1][j-1], // replace
                )
            }
        }
    }

    return dp[m][n]
}

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

Explanation

• We initialize the dp table such that converting a string to an empty string takes i operations.
• Then we fill the table using the recurrence relation.
• The final answer is at dp[m][n], representing the cost to convert the full word1 to word2.

Time and Space Complexity

MetricComplexityTime ComplexityO(m * n)Space ComplexityO(m * n)

Where m = len(word1) and n = len(word2).

Space Optimization (Optional)

Since each row only depends on the previous row, this can be optimized to use O(n) space. Let me know if you’d like that version too!

Conclusion

LeetCode 72 is a classic and crucial problem in the dynamic programming arsenal. It elegantly shows how we can build up optimal solutions using subproblems and handle complex scenarios like string transformations efficiently.

Solving this in Go is clean and intuitive using slices and nested loops.