两个字符串间公共最长子串的递归解
两个字符串间公共最长子串的递归解
提问于 2018-06-26 01:42:32
我试图返回两个字符串之间的公共子字符串的长度。我非常了解DP解决方案，但是我希望能够在实践中递归地解决这个问题。
我有办法找到最长的公共序列..。
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))但是，我需要最长的公共子字符串，而不是最长的普通字母序列。我试着用几种方式修改我的代码，其中一种是将基本情况更改为.
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。
我的递归技巧不是最棒的，所以如果有人能帮助我，那将是非常有帮助的。
回答 3
Stack Overflow用户
回答已采纳
发布于 2018-06-26 18:07:56
您需要分别对每一项进行递归。如果您有多个递归函数，这就更容易了。
def longest_common_substr_at_both_start (str1, str2):
if 0 == len(str1) or 0 == len(str2) or str1[0] != str2[0]:
return ''
else:
return str1[0] + longest_common_substr_at_both_start(str1[1:], str2[1:])
def longest_common_substr_at_first_start (str1, str2):
if 0 == len(str2):
return ''
else:
answer1 = longest_common_substr_at_both_start (str1, str2)
answer2 = longest_common_substr_at_first_start (str1, str2[1:])
return answer2 if len(answer1) < len(answer2) else answer1
def longest_common_substr (str1, str2):
if 0 == len(str1):
return ''
else:
answer1 = longest_common_substr_at_first_start (str1, str2)
answer2 = longest_common_substr(str1[1:], str2)
return answer2 if len(answer1) < len(answer2) else answer1
print(longest_common_substr("BAGGTXAYB","AGGTAB") )Stack Overflow用户
发布于 2018-08-02 13:16:29
包装algo.dynamic；
公共类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;
}}
Stack Overflow用户
发布于 2018-07-06 15:56:56
我非常地抱歉。我没有时间把它转换成递归函数。这是相对直接的写作。如果Python有一个fold函数，那么递归函数就会大大简化。90%的递归函数是原语。这就是为什么fold如此宝贵的原因。
我希望这其中的逻辑能够帮助实现递归版本。
(x,y)= "AGGTAB","BAGGTXAYB"
xrng= range(len(x)) # it is used twice
np=[(a+1,a+2) for a in xrng] # make pairs of list index values to use
allx = [ x[i:i+b] for (a,b) in np for i in xrng[:-a]] # make list of len>1 combinations
[ c for i in range(len(y)) for c in allx if c == y[i:i+len(c)]] # run, matching x & y...producing这个列表，从中获取最长的匹配
‘'AG'，'AGG'，'AGGT'，'GG'，'GGT'，'GT’
我不知道从名单上得到最长的比赛会有点牵扯。
ls= ['AG', 'AGG', 'AGGT', 'GG', 'GGT', 'GT']
ml= max([len(x) for x in ls])
ls[[a for (a,b) in zip(range(len(ls)),[len(x) for x in ls]) if b == ml][0]]"AGGT“
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51033803
复制相关文章
相似问题
腾讯云开发者
