回文字符串

[编程题]回文字符串

热度指数：9450 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

最大回文子串是被研究得比较多的一个经典问题。最近月神想到了一个变种，对于一个字符串，如果不要求子串连续，那么一个字符串的最大回文子串的最大长度是多少呢。

数据范围：字符串长度满足 $1 \le n \le 1000 \$ ，字符串中仅包含 0~9 和大小写字母

输入描述:

每个测试用例输入一行字符串（由数字0-9，字母a-z、A-Z构成），字条串长度大于0且不大于1000.

输出描述:

输出该字符串的最长回文子串的长度。（不要求输出最长回文串，并且子串不要求连续）

示例1

输入

adbca

输出

说明

因为在本题中，不要求回文子串连续，故最长回文子串为aba(或ada、aca)

备注:

因为不要求子串连续，所以字符串abc的子串有a、b、c、ab、ac、bc、abc7个

算法知识视频讲解

Python

贾志统

def max_sub_str_length(raw_str):
    dp = {}
    def length_from_l_to_r(l, r):
        if l == r:
            return 1
        if l > r:
            return 0
        if (l, r) in dp:
            return dp[(l, r)]
        sub_str_length = 0
        if raw_str[l] == raw_str[r]:
            sub_str_length = 2 + length_from_l_to_r(l+1, r-1)
        else:
            sub_str_length = max(length_from_l_to_r(l+1, r), length_from_l_to_r(l, r-1))
        dp[(l, r)] = sub_str_length
        return sub_str_length
    return length_from_l_to_r(0, len(raw_str)-1)


raw_str = input()
print(max_sub_str_length(raw_str))

发表于 2019-08-22 19:05:38 回复(0)