我试图返回两个字符串之间公共(public)子字符串的长度。我非常了解 DP 解决方案,但是我希望能够递归解决这个问题只是为了练习。
我有找到最长公共(public)子序列的解决方案...
def get_substring(str1, str2, i, j):
if i == 0 or j == 0:
return
elif str1[i-1] == str2[j-1]:
return 1 + get_substring(str1, str2, i-1, j-1)
else:
return max(get_substring(str1, str2, i, j-1), get_substring(str1, str2, j-1, i))
但是,我需要最长的公共(public)子串,而不是最长的公共(public)字母序列。我尝试以多种方式更改我的代码,其中一种是将基本情况更改为...
if i == 0 or j == 0 or str1[i-1] != str2[j-1]:
return 0
但这并没有奏效,我的其他尝试也没有奏效。
例如,对于以下字符串...
X = "AGGTAB"
Y = "BAGGTXAYB"
print(get_substring(X, Y, len(X), len(Y)))
最长的子串是AGGT。
我的递归技能不是最好的,所以如果有人能帮助我,那将非常有帮助。
最佳答案
包 algo.dynamic;
公共(public)类 LongestCommonSubstring {
public static void main(String[] args) {
String a = "AGGTAB";
String b = "BAGGTXAYB";
int maxLcs = lcs(a.toCharArray(), b.toCharArray(), a.length(), b.length(), 0);
System.out.println(maxLcs);
}
private static int lcs(char[] a, char[] b, int i, int j, int count) {
if (i == 0 || j == 0)
return count;
if (a[i - 1] == b[j - 1]) {
count = lcs(a, b, i - 1, j - 1, count + 1);
}
count = Math.max(count, Math.max(lcs(a, b, i, j - 1, 0), lcs(a, b, i - 1, j, 0)));
return count;
}
关于algorithm - 递归求解两个字符串之间的公共(public)最长子串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51033803/