面试指南——最长公共子串问题

题目:
给定两个字符串,求出它们之间最长的相同子字符串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
 * 公共子串需要连续,公共子序列不需要连续
 * dp矩阵第一列dp[0...M-1][0],如果str1[i]==str2[0],令dp[i][0]=1,否则dp[i][0]=0;
 * dp矩阵第一行dp[0][0...N-1],如果str1[0]==str2[j],令dp[0][j]=1,否则dp[0][j]=0;
 * 其他位置从左到右,从上到下计算,dp矩阵有以下两种情况:
 * a.如果str1[i]!=str2[j],说明在必须把str1[i]和str2[j]当做公共子串的最后一个字符是不可能的,所以dp[i][j]=0;
 * b.如果str1[i]==str2[j],说明str1[i]和str2[j]可以作为公共子串的最后一个字符,dp[i][j]=dp[i-1][j-1]+1;
 * 生成dp矩阵后,遍历dp矩阵,可以找到最大值及其位置,从而得到最长公共子串。
 * 因为公共子串是连续的,所以我们得到长度和结束位置后,可以通过substring函数获取最长公共子串
 *
 * 因为公共子串是连续的,所以在生成dp矩阵的过程中我们只用到了左上方的数,所以可以压缩为空间复杂度为O(1)的算法。
 * 每次计算一条斜线,并比较最长公共子串的长度,从第0行,chs2.length-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
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
public class 最长公共子串问题 {
    public static int[][] getdp(char[] str1, char[] str2) {
        int[][] dp = new int[str1.length][str2.length];
        for (int i = 0; i < str1.length; i++) {
            if (str1[i] == str2[0]) {
                dp[i][0] = 1;
            }
        }
        for (int j = 1; j < str2.length; j++) {
            if (str1[0] == str2[j]) {
                dp[0][j] = 1;
            }
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                if (str1[i] == str2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
        }
        return dp;
    }
    public static String lcst1(String str1, String str2) {
        if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
            return "";
        }
        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();
        int[][] dp = getdp(chs1, chs2);
        int end = 0;
        int max = 0;
        for (int i = 0; i < chs1.length; i++) {
            for (int j = 0; j < chs2.length; j++) {
                if (dp[i][j] > max) {
                    end = i;
                    max = dp[i][j];
                }
            }
        }
        return str1.substring(end - max + 1, end + 1);
    }
    //获取最长公共子串的优化算法
    public static String lcst2(String str1, String str2) {
        if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
            return "";
        }
        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();
        int row = 0; // 斜线开始位置的行
        int col = chs2.length - 1; // 斜线开始位置的列
        int max = 0; // 记录最大长度
        int end = 0; // 最大长度更新时,记录子串的结尾位置
        while (row < chs1.length) {
            int i = row;
            int j = col;
            int len = 0;
            // 从(i,j)开始向右下方遍历
            while (i < chs1.length && j < chs2.length) {
                if (chs1[i] != chs2[j]) {
                    len = 0;
                } else {
                    len++;
                }
                // 记录最大值,以及结束字符的位置
                if (len > max) {
                    end = i;
                    max = len;
                }
                i++;
                j++;
            }
            if (col > 0) { // 斜线开始位置的列先向左移动
                col--;
            } else { // 列移动到最左之后,行向下移动
                row++;
            }
        }
        return str1.substring(end - max + 1, end + 1);
    }
    public static void main(String[] args) {
        String str1 = "ABC1234567DEFG";
        String str2 = "HIJKL1234567MNOP";
        System.out.println(lcst1(str1, str2));
        System.out.println(lcst2(str1, str2));
    }
}
0 条评论
发表一条评论