python - 具有子回文长度的递归子回文

Question

我正在尝试创建一个递归函数，它计算最大的子回文。

例如最大的sub.Pal。 “角色”是“carac”。

到目前为止，我已经实现了我的目标，但仅使用全局变量“length”添加我的值，但如果有人可以向我展示如何仅通过递归调用来做到这一点，那就太好了。我首先尝试为该函数提供第二个参数(长度=0)，并在调用该函数时向其添加值，但我无法使其正常工作。

这是我的代码:

length = 0

def subpalindrom(s):
    global length
    if len(s) == 1:
        length += 1
        return True, length

    if len(s) == 0:
        return True, length

    elif s[0] != s[-1]:

        for i in range(len(s) - 1, int(len(s) / 2) - 1, -1):  # search right half, if there is smth. equal

        if s[0] == s[i]:
            length += 2
            return subpalindrom(s[1:i])  # if smth. is equal slice it, add length

        elif i == int(len(s) / 2):
            # if index i is at half of the string and nothing was found, continue with next val on left half
            return subpalindrom(s[1:])
    else:
        length += 2
        return subpalindrom(s[1:-1])


print(subpalindrom("character"))

如果有人能告诉我如何查看这个函数的时间复杂度，那就太好了。我想说它是 O(log n) 但这只是一个猜测。

编辑:T(n) = T(n-2) + n/2 ？T(n-2) 用于递归调用(因为我们切掉了 2 个元素)，而 + n/2 由于 for 循环？

感谢您的宝贵时间!

Answer 1

抱歉分享晚了，但如果有人感兴趣，我是这样处理的:

def subpalindrom(l, r, w):
    if l == r:
        return 1
    if l > r:
        return 0
    if w[l] == w[r]:
        return 2 + subpalindrom(l + 1, r - 1, w)
    else:
        return max(subpalindrom(l + 1, r, w), subpalindrom(l, r - 1, w))


print(subpalindrom(0, len("character")-1, "character"))