最长公共子序列LCS问题-蒲公英云

最长公共子序列LCS问题

冷不防 2022-09-17 15:21 314阅读 0赞

好久没有写博客了，刚才在网上看了清华大学的数据结构公开课，链接：https://www.xuetangx.com 可以注册个账号去听数据结构课程，老师讲的特好。

我的代码是按照老师讲的递归算法给了个java版本的实现（好久都没写c/c++代码了，手头也没有c++的IDE），通过java版本改c++或其他语言的版本也挺容易的。

递归是一种简单解法，刚开始理解会有困难，一个问题如果能简化为一个比原来问题规模小的问题和一个可以解决的问题，最后可以合并这两个问题的解得出原问题的解，那么

这样的一个问题可以用递归的方法来解决。

一个序列A[0,n]，一个序列B[0,m]可以分为三种情况来考虑：

（1）、如果n=-1或者是m=-1，那么它们的最长公共子序列是空“”;

（2）、如果A[n]=B[m]，那么这个问题其实可以简化为A[0,n-1],B[0,m-1]，比如求“hello”与“exlo”的最长公共子序列，其实可以转化为”hell”与”exl”的最大公共子序列，然后再把最后的”o”加上就可以求解出。

（3）、如果A[n]!=B[m]，那么可以转化为A[0,n-1)与B[0,m]或者是A[0,n]与[0,m-1),然后求出两者中的最长公共子序列。

清华大学的老师讲的很透彻，我在这表达的不是很清楚，爱学习的同学可以去这个链接：https://www.xuetangx.com 申请个账号，欣赏欣赏名校老师上课的风采。

public static void main(String[] args) {
        String leftSequence = "computer";
        String rightSequence = "cmhjkute";
        String s = recGetLCS(leftSequence, leftSequence.length()-1, 
                                        rightSequence, rightSequence.length()-1);
        System.out.println("*******");
        System.out.println(s);
        System.out.println("&&&&&&&&");
    }
    public static String recGetLCS(String leftSequence, 
                                        int indexL, String rightSequence, int indexR) {
        if (indexL < 0 || indexR < 0) {
            return "";
        }
        if (leftSequence.charAt(indexL) == rightSequence.charAt(indexR)) {
            String lcs = recGetLCS(leftSequence, indexL-1, rightSequence, indexR-1)
                                                         + leftSequence.charAt(indexL);
            return lcs;
        } else {
            String s1 = recGetLCS(leftSequence, indexL-1, rightSequence, indexR);
            String s2 = recGetLCS(leftSequence, indexL, rightSequence, indexR-1);
            if (s1.length() > s2.length()) {
                return s1;
            } else {
                return s2;
            }
        }
    }