代码之家 › 专栏 › 技术社区 › William Edwardson

最长重复子序列:边缘情况

subsequence dynamic-programming dynamic algorithm string

William Edwardson · 技术社区 · 2 年前

问题

在使用自下而上的动态编程解决最长重复子序列问题时,每当一个字母重复奇数次时,我就开始遇到边缘情况。

目标是使用不同索引处的元素找到字符串中出现两次的最长子序列。范围可以重叠但索引应该是不相交的(即。, str[1] , str[4] 和 str[2] , str[6] 可以是一个解决方案,但不是 str[1] , str[2] 和 str[2] , str[3] .

最小再现性示例

s = 'AXXXA'

n = len(s)

dp = [['' for i in range(n + 1)] for j in range(n + 1)]

for i in range(1, n + 1):
  for j in range(1, n + 1):
    if (i != j and s[i - 1] == s[j - 1]):
      dp[i][j] = dp[i - 1][j - 1] + s[i - 1]
    else:
      dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(dp[n][n])

问题

关于如何避免这种情况,有什么建议吗?

输入s=“AXXXA”时,答案应该是A或X,但最终结果返回XX,显然将第三个X与第一个X和第二个X配对。

错误启动

我不想在比赛中添加支票( s[i - 1] == s[j - 1] )看看是否 s[i - 1] in dp[i - 1][j - 1] 因为另一个输入可能类似于 AAJDDAJJTATA ,必须添加 A 两次

2 回复 | 直到 2 年前

user24714692 2 年前

为了检索最长的,最好实现一个新函数,结果为 dp 网格
你的算法很好,你只需要增加你的新算法 数据处理 通过1,当 s[i - 1] == s[j - 1] :

    n = len(s)
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if s[i - 1] == s[j - 1] and i != j:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[-1][-1]

如果你想构建最长的,你可以使用dp网格,只要 if s[i - 1] == s[j - 1] and i != j 满足,将char附加到最长的:

    def get_longest():
        i, j = n, n
        lrs = []
        while i > 0 and j > 0:
            if s[i - 1] == s[j - 1] and i != j:
                lrs.append(s[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

        return ''.join(lrs[::-1])

密码

def LRS(s):
    def get_longest():
        i, j = n, n
        lrs = []
        while i > 0 and j > 0:
            if s[i - 1] == s[j - 1] and i != j:
                lrs.append(s[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

        return ''.join(lrs[::-1])
    n = len(s)
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if s[i - 1] == s[j - 1] and i != j:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    print(get_longest())
    return dp[-1][-1]


s = 'AXXXA'
print(LRS(s))

打印

XX 2.

Nathan Davis 2 年前

事实上,你的初始算法及其答案是正确的(……但这是一个好问题,因为其他人可能会混淆LRS的含义)。

根据您的意见( in ),子序列( s1 , s2 是

in: AXXXA
s1:  XX
s2:   XX

所以 XX (长度2)确实是正确答案。

X 这将是问题的非重叠版本的正确答案,在该版本中,范围(而不仅仅是单个索引)必须是不相交的。

blhsing 2 年前

您可以跟踪最后添加的字符的索引,并确保当两个字符相同时,它们的索引不仅必须彼此不同,而且必须与最后添加的角色的索引不同:

s = 'AXXXA'
n = len(s)
dp = [[('', 0, 0) for i in range(n + 1)] for j in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        last = dp[i - 1][j - 1]
        if last[2] != i != j != last[1] and s[i - 1] == s[j - 1]:
            dp[i][j] = last[0] + s[i - 1], i, j
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], key=lambda t: t[0])

print(dp[n][n][0]) # outputs X

演示: https://ideone.com/mSKgKy