我想出了一个蛮力算法来寻找两个给定字符串之间的最长公共(public)子序列。看起来它的时间复杂度为 O(n^3)。它通过了我拥有的所有测试用例,但我仍然不确定它是否会通过所有测试用例.....请告诉我这是正确的蛮力算法吗?
public String lcs(String s1, String s2) {
int s2Start = 0;
StringBuilder result = new StringBuilder("");
StringBuilder temp = new StringBuilder("");
for(int s1Start = 0; s1Start < s1.length(); s1Start++) {
s2Start = 0; // reset
if(temp.length() > result.length()) {
result = temp;
}
temp = new StringBuilder(""); // reset
for(int i = s1Start; i < s1.length(); i++) {
char s1Char = s1.charAt(i);
for(int j = s2Start; j < s2.length(); j++) {
char s2Char = s2.charAt(j);
if(s1Char == s2Char) {
temp.append(Character.toString(s1Char));
s2Start = j + 1;
break;
}
}
}
}
if(temp.length() > result.length())
result = temp;
return result.toString();
}
如果上面的代码不对,我想要暴力算法返回最长的公共(public)子序列字符串,我该如何实现???
最佳答案
没有。这不是解决 LCS 问题的正确的蛮力算法。 看这个案例-
AKBLC
AMBNCK
这两个字符串的 LCS 答案应该是 3。 但在您的算法中,它将计算 2 (AK)。
关于java - 蛮力最长公共(public)子序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54264912/