NOC青少儿编程大赛Python复赛真题解析-最长的回文子串[解析]

欢迎大家来到IT世界,在知识的湖畔探索吧!

给你一个字符串s，找到s中最长的回文子串。

“如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。”

输入：s = “babad”

输出：”bab”

中心扩展算法

思路：回文字符串有两种类型，比如 aba 或者 abbc。

第一种是一个中心点往两边扩展；

第二种是两个中心点往两边扩展；

遍历中心点，使用双指针往两边扩展，如果两边的字母相同，就可以继续扩展；如果两边的字母不同，就停止扩展，取两种情况的最大子串

参考程序（kidscode.cn）：

def longestPalindrome(s): start, end = 0, 0 for i in range(len(s)): l1, r1 = expandAroundCenter(s, i, i) # 中心为奇数 b a b l2, r2 = expandAroundCenter(s, i, i + 1) # 中心为偶数 b aa b if r1 - l1 > end - start: start, end = l1, r1 if r2 - l2 > end - start: start, end = l2, r2 return s[start:end + 1] def expandAroundCenter(s, l, r): while l >= 0 and r < len(s) and s[l] == s[r]: # 字母相同，继续扩展 l -= 1 r += 1 return l + 1, r - 1 # 返回下标 s = "babab" print(longestPalindrome(s))

欢迎大家来到IT世界,在知识的湖畔探索吧!

如果有兴趣可以尝试动态规划的方法，仅提供思路。

动态规划

思路：使用动态规划算法解题步骤

定义状态：

我们可以定义 dp[i][j] 表示从索引 i 到 j 的子串是否为回文串。

初始化状态：

将所有长度为 1 的子串都初始化为回文，即 dp[i][i] = true。

检查所有长度为 2 的子串，如果两个字符相等，将 dp[i][i+1] 设为 true。

状态转移方程：

对于长度大于 2 的子串，dp[i][j] 是否为回文串取决于 dp[i+1][j-1] 和 s[i] == s[j]。

即dp[i][j] = dp[i+1][j-1] && s[i] == s[j]。

处理边界条件：

在上述初始化中已经处理了长度为 1 和 2 的情况。

自底向上构建解：

通过两层嵌套循环，自底向上地填充 dp 数组，从小规模子问题逐步构建到整个问题。

记录最优解：

在状态转移的过程中，不断更新记录最长回文子串的起始索引和长度。

返回结果：

最终，通过起始索引和长度，可以得到最长回文子串

原文少儿编程网（kidscode.cn）