mzoe666888

V1

2022/04/12阅读:31主题:兰青

内卷大厂系列《最小编辑距离问题二连击》

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

一、编辑距离概述

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

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

如果我们在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)

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1