题目描述

给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：

1.删除–将字符串A中的某个字符删除。
2.插入–在字符串A的某个位置插入某个字符。
3.替换–将字符串A中的某个字符替换为另一个字符。

现在请你求出，将A变为B至少需要进行多少次操作。

样例一 （样例参考leetcode 72 编辑距离）

输入 5
字符串一 : "horse";
输入 3
字符串二 : "ros";
输出 3
解释 : 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

输入 9
字符串一 : "intention";
输入 9
字符串二 : "execution";
输出 5
解释 : 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
----------

算法1

(动态规划) $O(n * m)$

首先我们需要找到状态转移方程

1. 设f[i][j]表示a[1,2,3 ...i]到b[1,2,3...j]的编辑距离

2. 如果a[i] = b[j]
a[1,2,3....i - 1,i]到b[1,2,3...j - 1,j] (默认前面修改好了) 
那么 f[i][j] = f[i - 1][j - 1] (表示不需要操作)

3.如果a[i] != b[j] (那么可以执行三种操作，修改，插入，删除)

3.1 修改  a[1,2,3....i - 1,i]
          b[1,2,3....j - 1,j] 
    把a[i]修改为b[j] , 那么f[i][j] = f[i - 1][j - 1] + 1;
样例   a = "lovt"  b = "love"; 前面操作已经把a[1,2,3...i - 1] 改变成了 b[1,2,3...j - 1];
        （f[i - 1][j - 1] 为把a的前 i - 1个字符修改为b的前j - 1个字符所需要的步骤）
        所以我们只需要执行 把 a[i] 修改成 b[j] 的操作 那么 f[i][j] = f[i - 1][j - 1] + 1
3.2 插入  a[1,2,3....i - 1,i]
          b[1,2,3....j - 1,j]
    在a[i]后插入b[j] , 那么 f[i][j] = f[i][j - 1] + 1;
样例  a = "lov" b = " love";前面操作已经把a[1,2,3...j - 1]改变成了 b[1,2,3,...j - 1,j]
         (f[i][j - 1]表示把a的前j - 1 个字符修改为b的前j - 1个字符所需要的步骤)
         最后我们只需要执行 在a[i] 之后插入b[j] f[i][j] = f[i][j - 1] + 1;
3.3 增加  a[1,2,3....i - 1,i]
          b[1,2,3....j - 1,j]
    在a[i]插入b[j] , 那么 f[i][j] = f[i - 1][j] + 1;
样例  a = "love" b = "lov" ;
      f[i][j] = f[i - 1][j] + 1;

光看文字大家可能不怎么理解，下面我给大家做一下表格把 ！！！hhh

     1  2  3  4  5
0    l  O  V  E  R
1 N  1  2  3  4  5   // 从第一行开始
2 O  2  1  2  3  4
3 T  3  2  2  3  4
4 V  4  3  2  3  4

时间复杂度O(n * m)

https://www.bilibili.com/video/BV1gk4y1177j?from=search&seid=8282711426839869063

Java 代码

import java.util.*;

public class Main {
    static int N = 1010;
    static int[][] f = new int[N][N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt() ;
        String a = sc.next();
        int m = sc.nextInt();
        String b = sc.next();
        for (int i = 1 ; i <= n ; i ++ ) f[i][0] = i;
        for (int j = 1 ; j <= m ; j ++ ) f[0][j] = j;

        for (int i = 1 ; i <= n ; i ++ ) {
            for (int j = 1 ; j <= m ; j ++ ) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1];
                }
                else {
                    f[i][j] = Math.min(f[i - 1][j] , f[i][j - 1]);
                    f[i][j] = Math.min(f[i][j] , f[i  -1][j - 1]) + 1;
                }
            }
        }
        System.out.println(f[n][m]);
    }
}

----------

### 算法2
##### (采用滚动数组的方式优化空间复杂度)  $O(n*m)$

blablabla

#### 时间复杂度

#### 参考文献


#### Java 代码
```java
import java.util.*;
public class Main {
    static int N = 1010;
    static int[] f = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        String a = sc.next();
        int n = sc.nextInt();
        String b = sc.next();
        for (int i = 1 ; i <= n ; i ++ ) f[i] = i;
        for (int i = 1 ; i <= m ; i ++ ) {
            int t1 = f[0] ++; // t1等价于 f[i - 1][0];
            for (int j = 1 ; j <= n ; j ++ ) {
                int t2 = f[j];
                if (a.charAt(i - 1) == b.charAt(j - 1)) 
                    f[j] = t1;
                else f[j] = Math.min(t1,Math.min(f[j - 1],f[j])) + 1;
                t1 = t2; // t1 = f[i - 1][j - 1];
            }
        }
        System.out.println(f[n]);
    }
}