HàPhan 河

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')
``````

Example 2:

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

Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
``````

## Solution

Use `dynamic programming`
Base case: Convert a `n` length string to an `empty` string needs `n` operations
General case:
If `dp[i-1][j-1]` is minimum operations count to convert `i-1` length string to `j-1` length string, then

1. When next characters are same, minimum operations will not be changed,
`dp[i][j] = dp[i-1][j-1]`
2. When next characters are not same, there're more 3 cases to consider
+ Insert: `dp[i][j] = dp[i][j - 1] + 1`
+ Replace: `dp[i][j] = dp[i - 1][j - 1] + 1`
+ Delete: `dp[i][j] = dp[i - 1][j] + 1`

Let's code!

``````class Solution {
func minDistance(_ word1: String, _ word2: String) -> Int {
if word1 == "" { return word2.count }
if word2 == "" { return word1.count }

let word1 = Array(word1)
let word2 = Array(word2)

let m = word1.count
let n = word2.count

var dp = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: m + 1)

for i in 1...m {
dp[i][0] = i
}

for j in 1...n {
dp[0][j] = j
}

for i in 1...m {
for j in 1...n {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]
} else {
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1
}
}
}

return dp[m][n]
}
}
``````