# Leetcode: Edit Distance

Edit Distance

<a href=”https://github.com/dennyzhang/code.dennyzhang.com/tree/master/problems/edit-distance“><img align=”right” width=”200″ height=”183″ src=”” /></a>

Similar Problems:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character

b) Delete a character

c) Replace a character

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution: dp – Time O(n*m), Space O(n*m)
```// Blog link: https://code.dennyzhang.com/edit-distance
// Basic Ideas: dp second order
//
// dp[i][j]: match word1 0:i with word2 0:j
// Then how we get dp[i][j] from previous caculation?
//     If word1[i] == word[j], dp[i-1][j-1]
//     Otherwise, we can make 3 choices
//       - Replace word1[i], dp[i-1][j-1]+1
//       - Delete word1[i-1], dp[i-1][j]+1
//       - Add word[j] to word1, dp[i][j-1]+1
// Complexity: Time O(n*m), Space O(n*m)
func minDistance(word1 string, word2 string) int {
len1, len2 := len(word1), len(word2)
if len1 == 0 || len2 == 0 { return len1+len2 }
dp := make([][]int, len1)
for i := range dp { dp[i] = make([]int, len2) }
// Initialize
if word1[0]!=word2[0] { dp[0][0] = 1 }
for j:=1; j<len2; j++ {
dp[0][j] = dp[0][j-1]+1
if word2[j] == word1[0] && dp[0][j] == j+1 {
dp[0][j] = j
}
}
for i:=1; i<len1; i++ {
dp[i][0] = dp[i-1][0]+1
if word1[i] == word2[0] && dp[i][0] == i+1 {
dp[i][0] = i
}
}
// dp
for i:=1; i<len1; i++ {
for j:=1; j<len2; j++ {
if word1[i] == word2[j] {
dp[i][j] = dp[i-1][j-1]
continue
}
min := dp[i-1][j-1]+1
if dp[i-1][j]+1 < min { min = dp[i-1][j]+1 }
if dp[i][j-1]+1 < min { min = dp[i][j-1]+1 }
dp[i][j] = min
}
}
return dp[len1-1][len2-1]
}
```

• Solution: dp – Time O(n*m), Space O(n)
```// Blog link: https://code.dennyzhang.com/edit-distance
// Basic Ideas: dp second order
//
// Two major improvements compared to intuitive dp[][]
// 1. We add a dummy " " to the head. Thus the logic of base cases can be dramatically simplified
// 2. Reduce space complexity from O(n*m) to O(n)
// Complexity: Time O(n*m), Space O(n)
func minDistance(word1 string, word2 string) int {
len1, len2 := len(word1), len(word2)
if len1 == 0 || len2 == 0 { return len1+len2 }
dp := make([]int, len2+1)
// initialize
for i:=0; i<=len2; i++ { dp[i] = i }
// dp
for i:=1; i<=len1; i++ {
prev := i-1
dp[0] = i
for j:=1; j<=len2; j++ {
cur := -1
if word1[i-1] == word2[j-1] {
cur = prev
} else {
// replace
cur = dp[j-1]+1
// delete
if prev+1 < cur { cur = prev+1 }
if dp[j]+1 < cur { cur = dp[j]+1 }
}
prev = dp[j]
dp[j] = cur
}
}
return dp[len2]
}
```

<div style=”overflow: hidden;”>

<div style=”float: left; padding: 5px”> <a href=”https://www.linkedin.com/in/dennyzhang001“><img src=”” alt=”linkedin” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://github.com/dennyzhang“><img src=”” alt=”github” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://www.dennyzhang.com/slack” target=”_blank” rel=”nofollow”><img src=”” alt=”slack”/></a></div>

</div>

Share It, If You Like It.