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

题目
给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB
则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
/*
* 以下dp[0…M-1]相当于dp[0]~dp[M-1]
* str1.length = M;str2.length = N ==>生成M*N大小的dp矩阵,
* dp[i][j]的含义:str1[0…i]和str2[0…j]的最长公共子序列的长度
* 从左到右,从上到下,计算dp矩阵
* 1.dp第一列即dp[0…M-1][0],dp[i][0]的含义是str1[0..i]和str2[0]的最长公共子序列的长度
* str2[0]只有一个字符,所以dp[i][0]最大为1,
* 如果str1[i]==str2[0] ==> dp[i][0]=1 ==> dp[i+1…M-1][0]=1;
* 2.dp第一行同第一列,如果str2[j] == str1[0] ==> dp[0][j]=1 ==> dp[0][j+1…N-1]=1;
* 3.其他位置的dp[i][j]有如下三种情况:
* a.可能是dp[i-1][j],代表str1[0…i-1]与str2[0…j]的最长公共子序列长度
* b.可能是dp[i][j-1],代表str1[0…i]与str2[0…j-1]的最长公共子序列的长度
* c.可能是dp[i-1][j-1]+1,当str1[i]==str2[j]时
* 4.dp矩阵右下角的值代表str1和str2整体的最长公共子序列长度,从右下角开始,有三种移动方式,向上、向左、向左上;i表示当前行数,j表示当前列数
* 5.如果dp[i][j] > dp[i-1][j]和dp[i][j-1],说明在计算dp[i][j]的时候选择了决策dp[i-1][j-1]+1,确定str1[i]=str2[j],
* 将该字符放入res,向左上方移动;
* 6.如果dp[i][j] == dp[i-1][j]说明之前dp[i-1][j-1]+1这个决策不是必须的选择,向上方移动即可;
* 7.如果dp[i][j] == dp[i][j-1]说明之前dp[i-1][j-1]+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
public class 最长公共子序列问题 {
    public static int[][] getdp(char[] str1,char[] str2){
        int[][] dp = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for(int i = 1;i < str1.length;i++) {
            dp[i][0] = Math.max(dp[i-1][0], str1[i] == str2[0] ? 1 : 0);
        }
        for(int j = 1;j < str2.length;j++) {
            dp[0][j] = Math.max(dp[0][j-1], str1[0] == str2[j] ? 1 : 0);
        }
        for(int i = 1;i<str1.length;i++) {
            for(int j = 1;j<str2.length;j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                if(str1[i] == str2[j]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);
                }
            }
        }
        return dp;
    }

    public static String lcse(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 m = chs1.length-1;
        int n = chs2.length-1;
        char[] res = new char[dp[m][n]];
        int index = res.length-1;
        while(index >= 0) {
            if(n > 0 && dp[m][n] == dp[m][n-1]) {
                n--;
            }else if(m > 0 && dp[m][n] == dp[m-1][n]) {
                m--;
            }else {
                res[index--] = chs1[m];
                m--;
                n--;
            }
        }
        return String.valueOf(res);    
    }
   
    public static void main(String[] args) {
        String str1 = "A1BC2D3EFGH45I6JK7LMN";
        String str2 = "12OPQ3RST4U5V6W7XYZ";
        System.out.println(lcse(str1, str2));

    }

}
0 条评论
发表一条评论