algorithm - 两个字符串所有可能的LCS(Longest Common Subsequence)

Question

我们可以用DP(动态规划)找到两个字符串的LCS(最长公共(public)子序列)。通过跟踪 DP 表，我们可以获得 LCS。但是，如果存在不止一个濒海战斗舰，我们如何获得所有的濒海战斗舰呢？

例子:

string1 : bcab
string2 : abc

这里的“ab”和“bc”都是LCS。

Answer 1

这是一个有效的 Java 解决方案。为了解释你可以看到我的答案 How to print all possible solutions for Longest Common subsequence

static int arr[][];
static void lcs(String s1, String s2) {
    for (int i = 1; i <= s1.length(); i++) {
        for (int j = 1; j <= s2.length(); j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1))
                arr[i][j] = arr[i - 1][j - 1] + 1;
            else
                arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
        }
    }
}

static Set<String> lcs(String s1, String s2, int len1, int len2) {
    if (len1 == 0 || len2 == 0) {
        Set<String> set = new HashSet<String>();
        set.add("");
        return set;
    }
    if (s1.charAt(len1 - 1) == s2.charAt(len2 - 1)) {
        Set<String> set = lcs(s1, s2, len1 - 1, len2 - 1);
        Set<String> set1 = new HashSet<>();
        for (String temp : set) {
            temp = temp + s1.charAt(len1 - 1);
            set1.add(temp);
        }
        return set1;
    } else {
        Set<String> set = new HashSet<>();
        Set<String> set1 = new HashSet<>();
        if (arr[len1 - 1][len2] >= arr[len1][len2 - 1]) {
            set = lcs(s1, s2, len1 - 1, len2);
        }
        if (arr[len1][len2 - 1] >= arr[len1 - 1][len2]) {
            set1 = lcs(s1, s2, len1, len2 - 1);
        }
        for (String temp : set) {
            set1.add(temp);
        }
        //System.out.println("In lcs" + set1);
        return set1;

    }
}


public static void main(String[] args) {
    String s1 = "bcab";
    String s2 = "abc";
    arr = new int[s1.length() + 1][s2.length() + 1];
    lcs(s1, s2);
    System.out.println(lcs(s1, s2, s1.length(), s2.length()));
}