LCS 问题的给定解决方案有什么问题？

Question

我有下面给出的两个字符串的最长公共子序列问题的递归解决方案：

def LCS(i, j, lcs): # i , j are the position of character in X and Y respectively which are being compared
                    # lcs is the string storing the current longest common subsequence
    print(i, j, lcs)
    if i == 0 or j == 0: # basic case
        return lcs

    if X[i - 1] == Y[j - 1]:  # increment lcs 
        lcs = X[i - 1] + lcs
        return lcs

  # else check for LCS(i-1,j) and LCS(i,j-1)

    lcs_copy = str(lcs)
    lcs1 = LCS(i - 1, j, lcs_copy)
    x = len(lcs1)
    lcs_copy = str(lcs)
    lcs2 = LCS(i, j - 1, lcs_copy)
    y = len(lcs2)

    if x > y:
        lcs = lcs1
    else:
        lcs = lcs2
    return lcs


X = 'abcbddab'
Y = 'bdcaba'
lcs = ''
lcs = LCS(8, 6, lcs)
print(lcs)

但它没有给出预期的结果。有什么建议可能是问题所在吗？

Answer 1

保留大部分 OP 代码，我们有两个更正：

基本情况需要递归调用
递归调用前无需复制字符串lcs

代码

def LCS(i, j, lcs):
  """i , j are the position of character in X and Y respectively which are being compared
      lcs is the string storing the current longest common substring"""

  # Base Cases
  if i == 0 or j == 0: # basic case
      return lcs

  if X[i - 1] == Y[j - 1]: 
      # add current string to longest of
      # precusor strings
      return LCS(i-1, j-1, X[i - 1] + lcs)

  # else: check for LCS(i-1,j) and LCS(i,j-1)
  lcs1 = LCS(i - 1, j, lcs)
  lcs2 = LCS(i, j - 1, lcs)

  if len(lcs1) > len(lcs2):
      return lcs1
  else:
      return lcs2

测试

X = 'abcbddab'
Y = 'bdcaba'
lcs = ''
lcs = LCS(8, 6, lcs)
print(lcs)  # Output: bdab

重写函数

函数应该是自包含的（不需要引用global X,Y）
使用PEP 8函数命名约定

重构代码

def lcs(str1, str2):
  """input strings str1, str2"""

  # Base Case
  if not str1 or not str2: # one is empty
      return ""

  if str1[-1] == str2[-1]: 
      # add current string to longest of
      # precusor strings
      return lcs(str1[:-1], str2[:-1]) + str1[-1]

  # else check for LCS(i-1,j) and LCS(i,j-1)
  return max(lcs(str1[:-1], str2), lcs(str1, str2[:-1]), key = len)

print(lcs('abcbddab', 'bdcaba'))
# Output: bcba (different longest sequence but same length)

LCS 问题的给定解决方案有什么问题？

whats the problem with the given solution to the LCS problem?

python

algorithm

longest-substring