May Leetcode Challenge - Day 31

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]
    }
}