最长回文串 Description 给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。 Input 输入：长度不大于100的非空字符串s，区分大小写.

### 寻找字符串中的最长回文子串 为了找到给定字符串中的最长回文子串，可以采用动态规划方法或者中心扩展法来解决这个问题。以下是两种常见的解决方案。 #### 方法一：动态规划 通过构建一个二维布尔数组 `dp` 来记录子串是否为回文。对于任意位置 `(i, j)` 的子串，当满足以下条件时认为其是一个回文子串： - 如果子串长度小于等于 2 并且两端字符相同，则该子串是回文[^1]。 - 对于更长的子串，只有当两端字符相同并且去掉两端后的内部部分也是回文时才成立。 下面是基于此逻辑的 Python 实现代码： ```python def longest_palindrome(s: str) -> str: n = len(s) if n < 2: return s start, max_len = 0, 1 dp = [[False]*n for _ in range(n)] for i in range(n): dp[i][i] = True for j in range(1, n): for i in range(j): if s[i] == s[j]: if j - i < 3 or dp[i+1][j-1]: dp[i][j] = True if dp[i][j] and (j - i + 1 > max_len): start = i max_len = j - i + 1 return s[start:start + max_len] ``` #### 方法二：中心扩展法 这种方法的核心思想是从每一个可能成为回文中心的位置出发向两侧扩展，直到无法继续构成回文为止。需要注意的是，回文中心可能是单个字符也可能是两个连续相同的字符[^4]。 下面提供了一个使用中心扩展技术求解最长回文子串的例子： ```python def expand_around_center(s: str, left: int, right: int) -> tuple: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return left + 1, right - 1 def longest_palindrome_expand(s: str) -> str: if not s or len(s) < 1: return "" start, end = 0, 0 for i in range(len(s)): l1, r1 = expand_around_center(s, i, i) # 奇数长度 l2, r2 = expand_around_center(s, i, i + 1) # 偶数长度 if r1 - l1 > end - start: start, end = l1, r1 if r2 - l2 > end - start: start, end = l2, r2 return s[start:end + 1] ``` 上述两种方法均能有效解决问题，并可根据实际需求选择适合的方式实现。注意，在某些特定场景下还需要考虑大小写敏感性等问题[^3]。