面试题

  • 在一个长字符串中，寻找一个短字符串，短字符串可能有一些噪音，即有的字段不匹配，且短字符串是长字符串长度的百分之一左右，如何快速查找到这个短字符串。
  • 当时面试官提示我编辑距离算法（露怯了，压根没听说过），后来看了一下，发现其实就是一道经典的DP，哎
  • 编辑距离算法衡量的是将一个字符串转换为另一个字符串所需的最少编辑操作次数，因为短字符串存在噪音，不会与长字符串中的子串完全匹配，所以我们可以筛选一定编辑次数内的子串。
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class EditDistanceSearch {
    /**
     * @param target     目标子串
     * @param longString 长字符串
     * @param threshold  容错阈值，即距离数，解决噪音问题
     * @return
     */
    public static List<String> findSimilarSubstrings(String target, String longString, int threshold) {
        // 结果集
        List<String> similarSubstrings = new ArrayList<>();
        // 遍历长字符串
        for (int i = 0; i < longString.length() - target.length(); i++) {
            // 取等长子串，计算编辑距离
            String substring = longString.substring(i, i + target.length());
            int distance = calculateEditDistance(substring, target);
            // 根据容错阈值筛选
            if (distance <= threshold)
                similarSubstrings.add(substring);
        }

        return similarSubstrings;
    }


    // 编辑距离算法
    public static int calculateEditDistance(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();

        // 初始化矩阵
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // 计算编辑距离
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        String target = "kitten";
        String longString = "skittlesittingbingocat";
        int threshold = 2;

        List<String> similarSubstrings = findSimilarSubstrings(target, longString, threshold);

        System.out.println("找到相似子串:");
        for (String substring : similarSubstrings) {
            System.out.println(substring);
        }
    }
}

概述

  • 编辑距离（Edit Distance），也称为Levenshtein距离，是衡量两个字符串之间相似度的一种常用算法。它衡量的是将一个字符串转换为另一个字符串所需的最少编辑操作次数，其中编辑操作可以是插入、删除或替换字符。
  • 其中一些常见的应用包括：
    1. 拼写纠错：通过计算目标单词与候选单词之间的编辑距离，可以找到最接近目标单词的正确拼写。
    2. 文本相似性：编辑距离可以用于比较两段文本之间的相似性，例如在文本搜索中匹配近似的关键词或在文档聚类中寻找相似的文本。
    3. 基因组比对：在生物信息学中，编辑距离可以用于比较DNA序列或蛋白质序列之间的相似性，从而进行基因组比对和分析。
    4. 语音识别：通过计算语音信号之间的编辑距离，可以在语音识别任务中找到最匹配的文本转录。
    5. 数据清洗：在数据处理中，可以使用编辑距离来清洗和规范化数据，例如纠正用户输入错误或匹配相似的实体名称。
  • 力扣题目链接：https://leetcode.cn/problems/edit-distance/
  • dp[i][j]表示的含义是，word1[i]变化到word2[j]花费的最少步数
    • 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
    • 当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
  • 上面的状态转移方程结合下面的表格来看
“” h o r s e
“” 0 1 2 3 4 5
r 1 1 2 2 3 4
o 2 2 1 2 3 4
s 3 3 2 2 2 3
  • 第一行
    1. 从""变化到""需要0步
    2. 从""变化到h需要花1步，插入一个h
    3. 从""变化到ho需要花2步，在2的基础上再插入一个o
    4. 从""变化到hor需要花3步，在3的基础上再插入一个r
    5. 以此类推
  • 第一列
    1. 从""变化到""需要0步
    2. 从r变化到""需要花1步，删除一个r
    3. 从ro变化到""需要花2步，在2的基础上再删除一个o
    4. 从r变化到""需要花3步，在3的基础上再删除一个s
  • 斜对角线
    1. 从""变化到""需要花0步
    2. 从r变化到h需要花1步，将r替换为h
  • 总结：dp[i-1][j-1]表示替换操作，dp[i-1][j]表示删除操作，dp[i][j-1]表示插入操作。
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
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // 初始化
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        // 计算编辑距离
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
        return dp[m][n];
    }
}

TODO

  • 新增一个分类，用于记录工作中遇到的算法。