最长公共子序列python2函数

Question

当我运行LCS（“人类”、“黑猩猩”）时，我得到的是“h”而不是“hm”。 当我运行LCS（'gattaca'，'taccaacta'），我得到的是“g”而不是“gaaca”。 当我运行LCS（'wow'，'whew'），我得到的是“ww”，这是正确的。 当我运行LCS（''，'whow'），我得到的是“”这是正确的。 当我运行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

多亏了实验室里我旁边的人！如果不时不时在堆栈溢出上碰到傲慢的人，那也不错。在

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

Answer 2

这不是你写LCS的方式。这就是如何编写一个非常奇怪的函数来计算第二个字符串中与第一个字符串的第一个字母相等的字母数。在

我相信你想写的东西是错的，所以这无关紧要，但如果我猜对了你要写的内容，你忘了在外部while循环中为j赋值0。在