代码之家 › 专栏 › 技术社区 › buydadip

两个字符串之间公共最长子串的递归求解

recursion algorithm

buydadip · 技术社区 · 7 年前

我试图返回两个字符串之间的公共子字符串的长度。我非常了解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)))

最长的子字符串是聚合 .

我的递归技巧不是最好的,所以如果有人能帮我,那将是非常有帮助的。

3 回复 | 直到 6 年前

btilly 7 年前

你需要分别在每一个上复发。如果有多个递归函数,则更容易执行此操作。

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") )

Nishant 6 年前

包algo.dynamic;

公共类LongesCommonSubString{

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;
}

}

fp_mora 7 年前

我很抱歉。我没有时间把它转换成递归函数。这是相对直接的组成。如果巨蟒有 fold 函数递归函数将大大简化。90%的递归函数是基元函数。这就是为什么 折叠 很有价值。

我希望本文中的逻辑对于递归版本有所帮助。

(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

…制作这个列表,从中选择最长的匹配项

['ag'、'agg'、'ag gt'、'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]]

“聚合”