NC92 最长公共子序列(二)_nc92 最长公共子序列(二) python

题目
知识点
动态规划
描述
给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列

示例1
输入：
“1A2C3D4B56”,“B1D23A456A”
返回值：
“123456”

示例2
输入：
“abc”,“def”
返回值：
“-1”

示例3
输入：
“abc”,“abc”
复制
返回值：
“abc”

示例4
输入：
“ab”,""
复制
返回值：
“-1”

细节讲解的博客地址：https://blog.csdn.net/hrn1216/article/details/51534607

思路：new一个二维的dp数组，存放两个字符串相同个数的。
1、我们发现，当两个字符串一样时，数组的对角线位置是依次加1的。说明当字符相同时，数据来源于左上角的位置+1。
2、若字符不相同，数据来源于左边或上边，取最大值。
3、寻找子序列，从后往前推，如果字符相同，那都减1。如果不同，从数组中往大的位置走，因为不同时，数据就来自较大的位置。

package mid;

public class LCS {

    public static void main(String[] args) {
        String lcs = lcs("13456778", "357486782");
        System.out.println(lcs);
    }
    public static String lcs (String s1, String s2) {
        // write code here
        int len1=s1.length();
        int len2=s2.length();
        if (len1==0 || len2==0){
            return "-1";
        }
        int[][] dp = new int[len1+1][len2+1];
        //第一行，一列 填0(默认赋值)
        for (int i = 1; i < len1 + 1; i++) {
            for (int j = 1; j < len2 + 1; j++) {
                if (s1.charAt(i-1)==s2.charAt(j-1)){
                    //假设字符串全部相同，那么矩阵的对角线上的点会依次加1，如果有相同字符时，数据来源是 左上角的数+1
                    dp[i][j] = dp[i-1][j-1]+1;
                }else {
                    //若不相同，那么数据来源可能是左边，也可能是上边，谁多取谁
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        //找出一个符合的子序列
        int length1 = len1;
        int length2 = len2;
        StringBuilder ans = new StringBuilder();
        //从后往前推
        while (length1>0 && length2>0){
            //如果字符相同就都减一
            if (s1.charAt(length1-1)==s2.charAt(length2-1)){
                ans.append(s1.charAt(length1-1));
                length1--;
                length2--;
            }else {
                //如果不同，那找大的那个方向,如果左边大于上面，那最右一列就无用了，所以length2--
                if (dp[length1][length2-1]>dp[length1-1][length2]){
                    length2--;
                }else {//如果左边小于等于上面，最下面一行就没用了
                    length1--;
                }
            }
        }
        if (ans.length()==0){
            return "-1";
        }
        return ans.reverse().toString();
    }
}


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