最长回文序列

Question

我尝试使用递归来解决它。这是我的代码。 "ABDA" 失败（返回 3 而不是 1）。这样做的原因对我来说很清楚，但我不确定如何解决。

def lps(s):
    print(s)
    n = len(s)
    if n <= 1:
        return n

    if s[0] == s[n-1]:
        return 2 + lps(s[1:-1])
    return max(lps(s[:-1]), lps(s[1:]))

Answer 1

该问题遗漏了一些信息，无法准确了解您在寻找什么。在下文中，我将假设您想要找到最长的同时也是后缀的前缀（以相反的顺序）。

递归地，想法是比较第一个和最后一个字符。如果它们不相等，则它不能是回文（在这种情况下，return 0）。如果它们相等，则 "palindromic part" 的长度是 1 + 剩余单词（即没有第一个和最后一个字符的单词）的 "palindromic part" 的长度：

def lps(word):
  if len(word) > 0 and word[0] == word[-1]:
    return 1 + lps(word[1:-1])
  else:
    return 0

print(lps('abc'))
print(lps('abca'))
print(lps('abba'))
print(lps('abcba'))
print(lps('abda'))

结果 0, 1, 2, 3, 1。

这些数字代表最长的前缀（以相反的顺序）也是后缀。

如你所见，"abba" 导致长度为 2（因为 "ab"），即使它是长度为 4 的回文。如果你想得到它的总长度回文，迭代进行可能更容易：

def lps_full(word):
  i = len(word)
  while i > 0:
    if word[:i] == word[:-i-1:-1]:
      return i
    i -= 1
  return 0

相同的示例导致 0, 1, 4, 5, 1，即，对于非回文的单词和回文的单词的长度与上述结果相同。

如果您必须要使用相同的函数，可以递归定义它：

def lps(word, i=0):
  if len(word) > i and word[i] == word[-i-1]:
    return lps(word, i+1)
  else:
    return i

最长回文序列

Longest Palindromic Subsequence

python

algorithm

computer-science