72. 最少编辑距离

题目描述

edit-distance

分析

Q1 我如何知道从一个单词 变成另外一个单词 需要做那个操作合适？插入|删除|替换 无限大问题 无法入手

每次操作一次字符 算一次编辑距离

操作次数o(n) 这是不是最优解

视频地址：https://www.youtube.com/watch?v=Q4i_rqON2-E

image.png https://leetcode.com/problems/edit-distance/discuss/25849/Java-DP-solution-O(nm) https://leetcode.com/problems/edit-distance/discuss/146320/cpp-dp-beats-99.9-8ms https://leetcode.com/problems/edit-distance/discuss/25846/20ms-Detailed-Explained-C++-Solutions-(O(n)-Space)

代码

go 递归

func minDistance(word1 string, word2 string) int {
   n := len(word1)
   m := len(word2)
   dp := make([][]int, n+1)
   for i := range dp {
       dp[i] = make([]int, m+1)
       //数组的(n-1,m-1)对应dp存储的(n,m)
   }

   return minDistanceDP(dp, word1, word2, n, m)
}

func minDistanceDP(dp [][]int, word1 string, word2 string, n int, m int) int {

   //一个空字符串变成字符串方式 只有一种 添加m个字符串
   if n == 0 {
       return m
   }

   if m == 0 {
       return n
   }
   //已经计算过的
   if dp[n][m] > 0 {
       return dp[n][m]
   }
   if word1[n-1] == word2[m-1] {
       //fun(abc)->fun(akc) ->fun(ab)->fun(ak)
       dp[n][m] = minDistanceDP(dp, word1, word2, n-1, m-1)

   } else {
       //一个字符串做A做一次变化操作变成字符串B 特点 字符A和字符串B 只有一个字符差异 其余都相同 寻找相部分
       //替换操作：fun(a)->func(b) 上个状态是空字符串fun("")->fun("")+替换操作 fun(i-1)->fun(j-1)的编辑距离
       //添加 fun(a)-fun(ab)  上个状态是fun(a)->fan(a) +添加操作 fun(i)->fun(j-1)的编辑距离
       //删除 fun(ab)-fun(a)  上个状态是fun(a)->fan(a) +删除操作操作  fun(i-1)->fun(j)的编辑距离
       replace := minDistanceDP(dp, word1, word2, n-1, m-1) + 1
       add := minDistanceDP(dp, word1, word2, n, m-1) + 1
       del := minDistanceDP(dp, word1, word2, n-1, m) + 1
       dp[n][m] = min(replace, min(add, del))
   }
   fmt.Println(word1, word2, n, m, dp[n][m])
   return dp[n][m]

}

go动态规划

func minDistance1(word1 string, word2 string) int {
    //We define the state dp[i][j] to be the minimum number of operations to convert word1[0..i - 1] to word2[0..j - 1]
    n := len(word1)
    m := len(word2)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
        //数组的(n-1,m-1)对应dp存储的(n,m)
    }
    // 默认值
    for i := 0; i <= n; i++ {
        dp[i][0] = i
    }
    for j := 0; j <= m; j++ {
        dp[0][j] = j
    }

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

        }
    }
    return dp[n][m]

}

总结

类似问题：

image.png

  61.One Edit Distance
Given two strings s and t, determine if they are both one edit distance apart.

Note: 

There are 3 possiblities to satisify one edit distance apart:

Insert a character into s to get t
Delete a character from s to get t
Replace a character of s to get t
Example 1:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.
Example 2:

Input: s = "cab", t = "ad"
Output: false
Explanation: We cannot get t from s by only one step.
Example 3:

Input: s = "1203", t = "1213"
Output: true
Explanation: We can replace '0' with '1' to get t.