Solving the LeetCode "Edit Distance" Problem in Go

Difficulty: Medium | Tags: String, Dynamic Programming

Introduction

The "Edit Distance" problem is a classic dynamic programming challenge that measures the minimum number of operations required to transform one string into another. This problem has practical applications in fields like natural language processing, bioinformatics, and spell-checking algorithms.

Problem Analysis

Given two strings, word1 and word2, we need to compute the minimum number of insertions, deletions, or replacements required to convert word1 into word2. For example, converting "horse" to "ros" requires three operations: replace 'h' with 'r', delete 'r', and delete 'e'.

Solution Approach

We use dynamic programming to solve this problem efficiently. The idea is to build a 2D table where dp[i][j] represents the minimum edit distance between the first i characters of word1 and the first j characters of word2. The table is filled iteratively by comparing characters and considering the cost of each operation (insert, delete, or replace).

Go Implementation

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], dp[i][j-1], dp[i-1][j-1])
            }
        }
    }
    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
}

Complexity Analysis

The time complexity of this solution is O(m*n), where m and n are the lengths of word1 and word2, respectively. This is because we fill a 2D table of size (m+1) x (n+1). The space complexity is also O(m*n) due to the storage requirements of the DP table.

Testing and Examples

Here are some test cases to validate the implementation:

• word1 = "horse", word2 = "ros" → Output: 3
• word1 = "intention", word2 = "execution" → Output: 5
• word1 = "", word2 = "abc" → Output: 3
• word1 = "abc", word2 = "" → Output: 3

Best Practices and Tips

When solving this problem, ensure you handle edge cases such as empty strings. Optimizing space complexity is possible by using a 1D array instead of a 2D table, but the 2D approach is more intuitive for understanding the problem. Always verify your solution with multiple test cases to ensure correctness.