少儿编程网

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

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

输入：s = "babad"

输出："bab"

中心扩展算法

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

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

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

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

参考程序：

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))

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

动态规划

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

定义状态：

我们可以定义 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 数组，从小规模子问题逐步构建到整个问题。

记录最优解：

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

返回结果：

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

本站内容未经许可，禁止任何网站及个人进行转载。