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

问题描述 投票:0回答:1

问题

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

目标是使用不同索引处的元素找到字符串中出现两次的最长子序列。范围可以重叠,但索引应该是不相交的(即

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
两次。

string algorithm dynamic dynamic-programming subsequence
1个回答
0
投票
  • 为了检索最长的,最好实现一个新函数,其结果为

    dp
    网格。

  • 你的算法没问题,你只需要将新的

    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
满足时,将字符附加到最长的:

    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

© www.soinside.com 2019 - 2024. All rights reserved.