英文:
Possible to have different Longest Common Subsequence for same pair of Strings?
问题
private static String[][] memo; // memoization
public static String lcsMemoized(String[] p, String[] q, int pLen, int qLen) {
String result = "";
// base case
if (pLen == 0 || qLen == 0) return "";
else if (memo[pLen][qLen] != null) return memo[pLen][qLen];
else if (p[pLen - 1].equals(q[qLen - 1])) {
// common last character
result = lcsMemoized(p, q, pLen - 1, qLen - 1) + p[pLen - 1];
} else {
String op1 = lcsMemoized(p, q, pLen - 1, qLen);
String op2 = lcsMemoized(p, q, pLen, qLen - 1);
if (op2.length() > op1.length()) result = op2;
else result = op1;
}
memo[pLen][qLen] = result;
return result;
}
请注意，上述代码仅为翻译，可能无法执行，因为它依赖于您提供的上下文和其他代码部分。
英文:
I have two input strings:
String1 = 3 9 8 3 9 7 9 7 0<br>
String2 = 3 3 9 9 9 1 7 2 0
Now, If I assess Left-To-Right, then LCS obtained : 3 3 9 9 7 0<br>
But, If I assess Right-To-Left, then another possible LCS: 3 9 9 9 7 0
Here's a picture to explain it (hopefully) better:
I wanted to understand if this is normal, or am I making a mistake ?
my code for generating LCS is below, which gives the Right-To-Left scenario output:
private static String[][] memo; // memoization
public static String lcsMemoized(String[] p, String[] q, int pLen, int qLen) {
String result = "";
// base case
if (pLen == 0 || qLen == 0) return "";
else if (memo[pLen][qLen] != null) return memo[pLen][qLen];
else if (p[pLen - 1].equals(q[qLen - 1])) {
// common last character
result = lcsMemoized(p, q, pLen - 1, qLen - 1) + p[pLen - 1];
} else {
String op1 = lcsMemoized(p, q, pLen - 1, qLen);
String op2 = lcsMemoized(p, q, pLen, qLen - 1);
if (op2.length() > op1.length()) result = op2;
else result = op1;
}
memo[pLen][qLen] = result;
return result;
}
答案1
得分: 0
可以完全可能有两个或更多的最长公共子序列。
一个简单的例子：1231和1321都有两个最长公共子序列：121和131。
英文:
It's perfectly possible to have two or more LCS.
A trivial example: 1231 and 1321 have 2 LCS: 121 and 131.
答案2
得分: 0
不仅可以有多个最长公共子序列（LCS），而且可能有很多个。考虑长度为 2m 的字符串，1 2 1 2 1 2 ... 1 2，以及另一个相同长度的字符串，2 1 2 1 2 1 ... 2 1。这两个字符串的最长公共子序列数量为 2^m！
英文:
Not only can there be multiple LCSs, there can be many. Consider the string of length 2m, 1 2 1 2 1 2 ... 1 2 and another string of the same length, 2 1 2 1 2 1 ... 2 1. The two of these have <code>2<sup>m</sup></code> LCSs!
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论