动态规划与中心扩展：解决LeetCode最长回文子串问题
在算法和数据结构的学习过程中，动态规划（Dynamic Programming，DP）是一种非常强大的技术。它通过将复杂问题分解为更小的子问题，并存储这些子问题的解，从而避免重复计算，提高算法效率。在LeetCode等编程竞赛平台中，动态规划问题非常常见。本文将围绕动态规划解决LeetCode上的“最长回文子串”问题，介绍中心扩展法，并详细解析代码实现。
问题分析
“最长回文子串”问题要求在一个字符串中找出最长的回文子串。回文串是指正读和反读都相同的字符串。例如，字符串“abba”是一个回文串，而“abcd”则不是。
动态规划法
传统的动态规划法通过构建一个二维数组dp，其中dp[i][j]表示字符串中从索引i到j的子串是否为回文串。具体实现如下：
1. 初始化一个二维数组dp，大小为n×n，其中n为字符串长度。
2. 遍历字符串的所有子串，对于每个子串，判断其是否为回文串，并更新dp数组。
3. 遍历dp数组，找到最大的回文子串长度。
这种方法的时间复杂度为O(n^2)，空间复杂度为O(n^2)。
中心扩展法
中心扩展法是一种更高效的方法，它通过以每个字符为中心，向两边扩展来寻找回文子串。这种方法的时间复杂度为O(n^2)，但空间复杂度可以降低到O(1)。
代码实现
以下是用中心扩展法解决“最长回文子串”问题的Python代码实现：
python
def longest_palindromic_substring(s: str) -> str:
if not s:
return ""
start, end = 0, 0
for i in range(len(s)):
扩展奇数长度的回文子串
len1 = expand_around_center(s, i, i)
扩展偶数长度的回文子串
len2 = expand_around_center(s, i, i + 1)
max_len = max(len1, len2)
if max_len > end - start:
start = i - (max_len - 1) // 2
end = i + max_len // 2
return s[start:end + 1]
def expand_around_center(s: str, left: int, right: int) -> int:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
返回回文子串的长度
return right - left - 1
代码解析
1. `longest_palindromic_substring`函数：遍历字符串中的每个字符，以该字符为中心，向两边扩展，寻找回文子串。更新最大回文子串的起始和结束索引。
2. `expand_around_center`函数：以给定字符为中心，向两边扩展，判断是否为回文子串。返回回文子串的长度。
总结
本文介绍了动态规划与中心扩展法解决LeetCode上的“最长回文子串”问题。中心扩展法具有时间复杂度和空间复杂度较低的优势，是一种高效解决该问题的方法。在实际应用中，可以根据具体问题选择合适的算法，提高代码效率。
Comments NOTHING