最长公共子序列 Python 2 函数

Question

当我运行 LCS（'human'、'chimp' ）时，我得到 "h" 而不是 "hm"。当我运行 LCS( 'gattaca', 'tacgaacta' ) 时，我得到 "g" 而不是 "gaaca"。当我运行 LCS( 'wow', 'whew' ) 时，我得到 "ww" 这是正确的。当我运行 LCS( '', 'whew' ) 时，我得到正确的 ""。当我运行 LCS( 'abcdefgh', 'efghabcd' ) 时，我得到 "a" 而不是 "abcd"。我做错了什么？

这是我的代码：

def LCS(S, T):
  array = ''
  i = 0
  j = 0
  while i < len(S):
    while j < len(T):
      if S[i] == T[j]:
        array += S[i]
      j += 1
    i += 1
  return array

Answer 1

这不是你写 LCS 的方式。这就是您编写非常奇怪的函数的方式，该函数计算第二个字符串中等于第一个字符串第一个字母的字母数。

我相信你的意思是错误的，所以这无关紧要，但如果我猜对了你的意思，你忘记在外部 while 循环中将 0 分配给 j。

Answer 2

感谢实验室里我旁边的人！不时不运行进入 Stack Overflow 上傲慢的人也很好。

def LCS(S, T):
  # If either string is empty, stop
  if len(S) == 0 or len(T) == 0:
    return ""

  # First property
  if S[-1] == T[-1]:
    return LCS(S[:-1], T[:-1]) + S[-1]

  # Second proprerty
  # Last of S not needed:
  result1 = LCS(S[:-1], T)
  # Last of T not needed
  result2 = LCS(S, T[:-1])
  if len(result1) > len(result2):
    return result1
  else:
    return result2

最长公共子序列 Python 2 函数

Longest Common Subsequence Python 2 function

python

lcs

python-2.7