Leetcode - Edit Distance

https://leetcode.com/problems/edit-distance/

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

Example 1:

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

func minDistance(word1 string, word2 string) int {
    m := len(word1)
    n := len(word2)
    dp := make([][]int, m+1)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]int, n+1)
    }
    for i := 0; i <= m; i++ {
        for j := 0; j <= n; j++ {
            if i == 0 {
                dp[i][j] = j
            } else {
                if j == 0 {
                    dp[i][j] = i
                }
            }
            if i > 0 && j > 0 {
                if word1[i-1] != word2[j-1] {
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])
                } else {
                    dp[i][j] = dp[i-1][j-1]
                }
            }
        }
    }
    
	return dp[m][n]
}

func min(nums ...int) int {
	minNum := math.MaxInt32
	for _, n := range nums {
		if minNum > n {
			minNum = n
		}
	}
	return minNum
}

• 相关文章
• 全局相关文章