我们可以用DP(动态规划)求出两个字符串的LCS(最长公共子序列)。通过跟踪 DP 表,我们可以获得 LCS。但如果存在不止一艘濒海战斗舰,我们怎样才能获得全部呢?
Example:
string1 : bcab
string2 : abc
这里“ab”和“bc”都是LCS。
这是一个有效的 java 解决方案。具体解释可以看我的回答如何打印最长公共子序列的所有可能解决方案 https://stackoverflow.com/questions/22299345/how-to-print-all-possible-solutions-for-longest-common-subsequence/26718032#26718032
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()));
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)