Python算法：寻找字符串中最长回文子串

本文档探讨的是一个经典的计算机科学问题——寻找字符串中的最长回文子串。回文是指正读反读都一样的字符序列，例如 "aba"、"racecar" 等。在给定的 IT 技术背景下，这个问题通常被用于算法设计，特别是动态规划或者中心扩散法等解决方案的学习和实践。 **问题描述** 题目要求我们编写一个程序，输入一个字符串 `s`，其长度范围在1到1000之间，且仅包含数字和大小写字母。目标是找到字符串中长度最长的回文子串。提供的示例帮助理解问题的要求： 1. 示例1: 输入 "babad"，输出 "bab"，因为 "bab" 是最长的回文子串，尽管 "aba" 也是符合条件的。 2. 示例2: 输入 "cbbd"，输出 "bb"，这是最长的回文子串。 3. 示例3: 输入 "a"，输出 "a"，单个字符本身就是回文。 4. 示例4: 输入 "ac"，输出 "a"，因为 "a" 是长度为1的回文，即使 "aa" 不满足条件。 **算法详解** 给出的参考代码使用了中心扩散的方法，具体实现了一个名为 `Solution` 的类。核心函数 `expand` 负责检查给定子串 `s[L...R]` 是否为回文。通过左右指针 `L` 和 `R` 同时向中心收缩，当遇到不匹配的字符时停止，并返回子串长度。这个过程在字符串的每个字符上进行，考虑了单个字符和相邻字符组成的子串。 `longestPalindrome` 函数遍历整个字符串 `s`，初始化 `start` 和 `maxLen` 分别表示当前最长回文子串的起始位置和长度。对于每个字符 `i`，先计算以 `i` 和 `i` 为中心的回文子串长度 `len1`，再计算以 `i` 和 `i+1` 为中心的长度 `len2`，取两者中的较大值作为当前子串长度 `len`。如果 `len` 大于当前最长回文长度 `maxLen`，则更新 `start` 和 `maxLen`。最后返回以 `start` 为起始位置、长度为 `maxLen` 的最长回文子串。 总结起来，解决这个问题的关键在于利用回文的对称性，通过迭代检查不同长度的子串来找到最长的回文部分。这种方法具有较高的时间复杂度，理论上是 O(n^2)，其中 n 是字符串长度，但在实际应用中由于终止条件的提前，效率通常可以优化到接近线性。此算法是动态规划的一种经典应用，在数据结构和算法学习中具有很高的实用价值。