Jamzen的技术博客
0%

LeetCode.编辑距离

发表于 分类于 Valine：

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
  1. 示例 1：
    输入：word1 = “horse”, word2 = “ros”，输出：3
    解释：
  • horse -> rorse (将 ‘h’ 替换为 ‘r’)
  • rorse -> rose (删除 ‘r’)
  • rose -> ros (删除 ‘e’)
  1. 示例 2：
    输入：word1 = “intention”, word2 = “execution”，输出：5
    解释：
  • intention -> inention (删除 ‘t’)
  • inention -> enention (将 ‘i’ 替换为 ‘e’)
  • enention -> exention (将 ‘n’ 替换为 ‘x’)
  • exention -> exection (将 ‘n’ 替换为 ‘c’)
  • exection -> execution (插入 ‘u’)

动态规划解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
object MinDistance {
     def main(args: Array[String]): Unit = {
          println(minDistance("horse", "ros"))
     }

     /**
      * 时间复杂度O(mn)
      * 空间复杂度O(mn)
      */
     def minDistance(word1: String, word2: String): Int = {
          val m = word1.length
          val n = word2.length

          val dp = new Array[Array[Int]](m + 1)
          for (i <- 0 to m) {
               dp(i) = new Array[Int](n + 1)
               dp(i)(0) = i
               if (i == 0) {
                    for (j <- 0 to n) {
                         dp(0)(j) = j
                    }
               }
          }
          
          for (i <- 1 to m) {
               for (j <- 1 to n) {
                    dp(i)(j) = Math.min(
                         Math.min(dp(i - 1)(j) + 1, dp(i)(j - 1) + 1),
                         if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp(i - 1)(j - 1) else dp(i - 1)(j - 1) + 1
                    )
               }
          }

          dp(m)(n)
     }
}