1

我正在处理的问题在这里： http: //practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/longestCommonSubsequence

基本上我们得到了两个字符串，我们被要求找到最长的公共子序列。我在网上搜索了解决方案并将它们与我自己的解决方案进行了比较，但我在我的代码中找不到任何错误。我想知道为什么它仍然不起作用。

而且，我被要求通过使用递归方法来解决这个问题

这是我的代码：

public static String longestCommonSubsequence(String a, String b){
    if(a.isEmpty() || b.isEmpty()){
        return "";
    }
    if (a.substring(a.length() - 1).equals(b.substring(b.length() - 1))){
        return longestCommonSubsequence(a.substring(0, a.length() - 1), b.substring(0, b.length()
                       - 1)) + a.substring(a.length() - 1);
    } else {
        String first = longestCommonSubsequence(a, b.substring(b.length() - 1));
        String second = longestCommonSubsequence(a.substring(a.length() - 1), b);
        if(first.length() > second.length()){
            return first;
        }
        return second;
    }
}

以下是所有测试用例：

调用值返回

“ABCDEFG”、“BGCEHAF”、“BCEF”

“她卖”、“贝壳”、“卖”

“12345”、“54321 21 54321”、“123”

《白眼老师》、《好吃的桃子》、《各显神通》

“马蒂”、“海伦”“”

"","乔" ""

“苏西”、“”“”

“ACGGTGTCGTGCTA”、“CGTTCGGCTATCGTACGT”、“CGGTTCGTGT”

使用我的代码，我得到了所有测试用例的 StackOverFlow。

4

2 回答 2

0

你应该a.substring()改为a.charAt()

public static String LCS_r(String a, String b) {
    int m = a.length() - 1;
    int n = b.length() - 1;

    if (m < 0 || n < 0)
        return "";

    if (a.charAt(m)==b.charAt(n)) {
        return LCS_r(a.substring(0, m), b.substring(0, n)) + a.substring(m);
    } 
    else {
        String s1 = LCS_r(a, b.substring(0, n));
        String s2 = LCS_r(a.substring(0, m), b);
        if (s1.length() > s2.length()) {
            return s1;
        } else {
            return s2;
        }
    }
于 2021-01-26T19:11:31.677 回答
0

您的 LCS 计算不正确。在 LCS 中，您需要从字符串末尾进行比较。如果两个字符串的最后一个字符匹配，则意味着它将成为 LCS 的一部分。

public static String longestCommonSubsequence(String a, String b) {
        int alength = a.length() - 1;
        int blength = b.length() - 1;

        if (alength < 0 || blength < 0)
            return "";

        if (a.substring(alength).equals(b.substring(blength))) {
            return longestCommonSubsequence(a.substring(0, alength), b.substring(0, blength))
                    + a.substring(alength);
        } else {
            String first = longestCommonSubsequence(a, b.substring(0, blength));
            String second = longestCommonSubsequence(a.substring(0, alength), b);
            if (first.length() > second.length()) {
                return first;
            } else {
                return second;
            }
        }
    }
于 2016-11-22T20:03:54.753 回答