在使用自下而上的动态规划解决最长重复子序列问题时,每当一个字母重复奇数次时,我就开始遇到边缘情况。
目标是使用不同索引处的元素找到字符串中出现两次的最长子序列。范围可以重叠,但索引应该是不相交的(即
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
两次。
为了检索最长的,最好实现一个新函数,其结果为
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