最长公共子序列Python 2函数

Question

当我运行LCS( 'human'，‘I’)时，我得到的是"h“而不是"hm”。当我运行LCS( 'gattaca'，'tacgaacta‘)时，我得到的是"g“而不是"gaaca”。当我运行LCS(‘哇’，‘呼’)时，我得到的是"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

多亏了实验室里坐在我旁边的人，我才弄明白了！如果不是偶尔在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

Answer 2

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

我相信你想写的东西是错的，所以这并不重要，但是如果我正确地猜对了你想写的东西，你忘了在外部的while循环中给j赋值为0。