LeetCode 5.最长回文子串

题目描述

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

示例 1:

输入: s = "babad"
输出: "bab"
解释: "aba" 也是一个有效答案。

示例 2:

输入: s = "cbbd"
输出: "bb"

说明:

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

Java 实现代码

java">public class Solution {public String longestPalindrome(String s) {if (s == null || s.length() < 1) {return "";}int start = 0, end = 0;  // 最长回文子串的起始和结束位置for (int i = 0; i < s.length(); i++) {int len1 = expandAroundCenter(s, i, i);    // 以单个字符为中心int len2 = expandAroundCenter(s, i, i + 1); // 以两个字符为中心int len = Math.max(len1, len2);if (len > (end - start)) {start = i - (len - 1) / 2;end = i + len / 2;}}return s.substring(start, end + 1);}// 中心扩展法private int expandAroundCenter(String s, int left, int right) {while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;}return right - left - 1;  // 返回回文串的长度}
}

解题思路

该问题的核心是寻找字符串中最长的回文子串。回文子串的特点是从前向后和从后向前的字符相同。我们可以用几种方法来求解此问题，最常见的解法是通过
中心扩展法 来解决。

中心扩展法

1. 回文的特点： 一个回文串可以通过其中心向两边扩展。例如，回文串 "aba" 的中心是 "b"，从中间扩展出去，得到回文串。

2. 中心扩展法的核心思想：

   • 每个字符（或每两个字符之间）可以看作回文的中心。
   • 从该中心开始，尝试向左右两侧扩展，找到最大长度的回文子串。

3. 具体步骤：

   • 对于每个字符 i，考虑两种情况：
     • 以字符 i 为中心的奇数长度回文串。
     • 以字符 i 和 i+1 为中心的偶数长度回文串。
   • 使用一个函数 expandAroundCenter(left, right) 来扩展回文串。
   • 对每个字符中心调用扩展函数，记录最大长度的回文子串。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是字符串的长度。每次扩展时的时间复杂度为 O(n)，总共需要执行 n 次扩展。
• 空间复杂度：O(1)，只使用了常数空间来存储一些变量，不依赖于输入数据的大小。