大厂高频算法面试题：《最小编辑距离系列》，您将学到什么是编辑距离，什么是最小编辑距离以及它能解决什么问题，有哪些实际的运用场景。

一、编辑距离概述

两个字符串之间有多相似？

在搜索引擎中，我们总会有偶尔拼错单词的情况，但我们会发现，即便我们拼错了，搜索引擎也能正确地显示出我们想要的结果，而且还会温馨地给出拼写错误的提示。

如果我们在Google中检索”Gooogle”，我们会看到如下结果。

Showing results for google

Search instead for gooogle

Google知道我们输错了，但是它是怎么知道我们输错的呢？

类似的场景还有很多，我们可以从中抽取出一个共通的问题，即从一个字符串转变为另一个字符串，需要经过怎样的编辑操作。

编辑距离和最小编辑距离

为了解决该问题，我们引入了编辑距离的概念，所谓的编辑距离，就是从串A转换到串B所需的编辑操作次数。

这里的编辑操作包括：

• 插入
• 删除
• 替换

而最小编辑距离（Minimum Edit Distance）就很容易理解了，就是从串A转换到串B所需的最少编辑操作次数（对应的代价）之和。

二、最小编辑距离 I

给定两个字符串str1和str2，再给定三个整数ic、dc和rc，分别代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。

【举例】

• str1="abc"，str2="adc"，ic=5，dc=3，rc=2，从"abc"编辑成"adc"，把'b'替换成'd'是代价最小的，所以返回2
• str1="abc"，str2="adc"，ic=5，dc=3，rc=100，从"abc"编辑成"adc"，先删除'b'，然后插入'd'是代价最小的，所以返回8
• str1="abc"，str2="abc"，ic=5，dc=3，rc=2，不用编辑了，本来就是一样的字符串，所以返回0

1、分析

ic：insertCost插入代价，dc：deleteCost删除代价，rc：replaceCost替换代价。

样本对应模型：str1样本做行，str2样本做列，根据结尾分析可能性，以什么什么结尾考虑入手。

dp[i][j]含义：str1拿出前缀为i长度的字符串 变成 str2拿出前缀为j长度的字符串的 最小编辑代价是多少？

前缀必须是连续的！毫无疑问的！

dp[0][0]格子代表str1中取前缀为0的字符串变成str2中取前缀为0的字符串，即0长度的字符串str1变成0长度的字符串str2，不需要代价，dp[i][j] = 0

dp第一行的格子怎么填？ 第一行的格子i都为0，代表长度为0的字符串str1怎么变成长度为0~j-1的字符串str2，只能发生插入操作（ic）

dp第一列的格子怎么填？ 第一列的格子j都为0，代表长度为0~i-1的字符串str1怎么变成长度为0的字符串str2，只能发生删除操作（dc）

除了第一行和第一列之外，剩下的格子怎么填？分析可能性如下：

样本对应模型往往考虑结尾位置，考虑str1的结尾，如果str1的长度为i，那么下标为0~i-1，保留i-1位置的字符和不保留i-1位置的字符

• 可能性一：如果i-1的字符和j-1的字符一样，那么不需要代价，dp[i][j] = dp[i-1][j-1]
• 可能性二：如果i-1的字符和j-1的字符不一样，那么需要替换一个字符的代价，dp[i][j] = dp[i-1][j-1] + 1个替换代价
• 可能性三：让i-1前边的字符串（0~i-2）先变成j长度的字符串，然后删除str1的最后一个字符，dp[i][j] = dp[i-1][j] + 1个删除代价
• 可能性四：先让str1的整体变成str2的前缀，然后再加一个字符，dp[i][j] = dp[i][j-1] + 1个插入代价

剩下的格子中，每个格子的最小代价：4种可能性中PK谁小

最终返回dp[N-1][M-1]：就是str1变成str2的最小代价。

2、实现

public static int minCost(String s1, String s2, int ic, int dc, int rc) {
    if (s1 == null || s2 == null) {
        return 0;
    }
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    int N = str1.length + 1;
    int M = str2.length + 1;
    int[][] dp = new int[N][M];
    // dp[0][0]  = 0
    for (int i = 1; i < N; i++) { // 第一列格子：整数倍的删除代价
        dp[i][0] = dc * i;
    }
    for (int j = 1; j < M; j++) { // 第一行格子：整数倍的插入代价
        dp[0][j] = ic * j;
    }
    // 其余格子
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
            if (str1[i - 1] == str2[j - 1]) { // 可能性一：最后一个字符相等
                dp[i][j] = dp[i - 1][j - 1];
            } else { // 可能性二：最后一个字符不等，需要一个替换代价
                dp[i][j] = dp[i - 1][j - 1] + rc;
            }
            dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc); // 可能性三
            dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic); // 可能性四
        }
    }
    return dp[N - 1][M - 1];
}

三、最小编辑距离 II

给定两个字符串s1和s2，问s2最少删除多少字符可以成为s1的子串？

比如 s1 = "abcde"，s2 = "axbc"

返回1，s2删掉'x'就是s1的子串了。

1、分析

方法一：根据s2的长度状况分析，如果s2的长度很短的话，那就生成s2的所有子序列，然后用KMP算法判断子序列是否是s1的子串，如果有多个子序列是s1的字串，把即是s1的子串又是最长的子序列找到，s2的长度减去子序列的长度就是最少要删除几个字符

如果s2的长度为M，生成s2的所有子序列时间复杂度为O(2^M)，每生成一个子序列用KMP算法匹配，假如s1的长度为N，那么整体的时间复杂度为O(N*2^M)

方法二：假如s1的长度为N，s2的长度为M，那么生成s1的子串的时间复杂度为O(N²)，那么s1至少要插入几个字符变为s2的问题，也就是最小编辑距离问题（只有插入操作），假如子串的长度为K，那么需要构建K*M的二维表，子串的个数为N/2，所以总体时间复杂度为O(N² * N/2 * M) = O(N³ * M)

s1的子串插几个就代表s2要删除几个字符

2、实现

2.1、方法一

public static int minCost1(String s1, String s2) {
    List<String> s2Subs = new ArrayList<>();
    process(s2.toCharArray(), 0, "", s2Subs);
    s2Subs.sort(new LenComp()); // s2的所有子序列长度从大到下排序
    for (String str : s2Subs) {
        if (s1.indexOf(str) != -1) { // indexOf底层和KMP算法代价几乎一样，也可以用KMP代替
            return s2.length() - str.length();
        }
    }
    return s2.length();
}

// 生成str2的所有子序列：当前位置要还是不要问题
public static void process(char[] str2, int index, String path, List<String> list) {
    if (index == str2.length) {
        list.add(path); // 收集答案
        return;
    }
    // 不要当前位置的字符
    process(str2, index + 1, path, list);
    // 要当前位置的字符
    process(str2, index + 1, path + str2[index], list);
}

public static class LenComp implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        return o2.length() - o1.length();
    }

}

2.2、方法二

public static int minCost2(String s1, String s2) {
    if (s1.length() == 0 || s2.length() == 0) {
        return s2.length();
    }
    int ans = Integer.MAX_VALUE;
    char[] str2 = s2.toCharArray();
    for (int start = 0; start < s1.length(); start++) {
        for (int end = start + 1; end <= s1.length(); end++) {
            // str1[start....end]
            // substring -> [ 0,1 )
            ans = Math.min(ans, distance(str2, s1.substring(start, end).toCharArray()));
        }
    }
    return ans == Integer.MAX_VALUE ? s2.length() : ans;
}

// 求str2到s1sub的编辑距离
// 假设编辑距离只有删除动作且删除一个字符的代价为1
public static int distance(char[] str2, char[] s1sub) {
    int row = str2.length;
    int col = s1sub.length;
    int[][] dp = new int[row][col];
    // dp[i][j]的含义：
    // str2[0..i]仅通过删除行为变成s1sub[0..j]的最小代价
    // 可能性一：
    // str2[0..i]变的过程中，不保留最后一个字符(str2[i])，
    // 那么就是通过str2[0..i-1]变成s1sub[0..j]之后，再最后删掉str2[i]即可 -> dp[i][j] = dp[i-1][j] + 1
    // 可能性二：
    // str2[0..i]变的过程中，想保留最后一个字符(str2[i])，然后变成s1sub[0..j]，
    // 这要求str2[i] == s1sub[j]才有这种可能, 然后str2[0..i-1]变成s1sub[0..j-1]即可
    // 也就是str2[i] == s1sub[j] 的条件下，dp[i][j] = dp[i-1][j-1]
    dp[0][0] = str2[0] == s1sub[0] ? 0 : Integer.MAX_VALUE; // 如果相等则删除0个字符，不等无法删除
    for (int j = 1; j < col; j++) { // 第一行格子，str2长度为0，不可能有删除操作
        dp[0][j] = Integer.MAX_VALUE;
    }
    for (int i = 1; i < row; i++) { // 第一列格子
        dp[i][0] = (dp[i - 1][0] != Integer.MAX_VALUE || str2[i] == s1sub[0]) ? i : Integer.MAX_VALUE;
    }
    // 剩下的格子
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            dp[i][j] = Integer.MAX_VALUE;
            if (dp[i - 1][j] != Integer.MAX_VALUE) {
                dp[i][j] = dp[i - 1][j] + 1; // s1删除一个字符的行为
            }
            if (str2[i] == s1sub[j] && dp[i - 1][j - 1] != Integer.MAX_VALUE) {
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]); // 左上角格子
            }
        }
    }
    return dp[row - 1][col - 1];
}

还能优化：每次生成s1的子串时，可以复用dp，不需要每次都重新创建一份。

每次生成s1的子串，对应生成的二维表，再二维表后边添加一行

0~0，0~1，0~2，0~N-1，每次在二维表的基础上添加一行

1~1，1~2，1~3，1~N-1，每次在二维表的基础上添加一行

...

N-1

时间复杂度能降一阶，O(N² * M)