LeetCode-in-Scala.github.io

72. Edit Distance

Hard

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• 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’)

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

Solution

object Solution {
    def minDistance(w1: String, w2: String): Int = {
        val n1 = w1.length
        val n2 = w2.length

        if (n2 > n1) {
            return minDistance(w2, w1)
        }

        val dp = Array.range(0, n2 + 1)

        for (j <- 0 to n2) {
            dp(j) = j
        }

        for (i <- 1 to n1) {
            var pre = dp(0)
            dp(0) = i

            for (j <- 1 to n2) {
                val tmp = dp(j)
                dp(j) =
                    if (w1(i - 1) != w2(j - 1))
                        1 + Math.min(pre, Math.min(dp(j), dp(j - 1)))
                    else
                        pre
                pre = tmp
            }
        }

        dp(n2)
    }
}

This site is open source. Improve this page.