题目

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

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

提示：

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

实现代码

使用双指针方式，遍历字符串，每次都向两边扩散，判断是否形成回文串，并保存最大长度的回文字串，直到遍历结束；

注意：回文字串的大小可能为奇数或偶数，所以每次遍历都要考虑两种情况；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public String longestPalindrome(String s) {

    String maxStr = "";
    for (int i = 0; i < s.length(); i++) {
      int left = i;
      int right = i;
      while (left >= 0 && right <= (s.length() - 1) && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
      }
      // 再来一次，考虑到回文字串是偶数个字符，那么left和righ初始就不能在同一位置
      maxStr = maxStr.length() > (right - left - 1) ? maxStr : s.substring(left + 1, right);
      left = i;
      right = i + 1;
      while (left >= 0 && right <= (s.length() - 1) && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
      }
      maxStr = maxStr.length() > (right - left - 1) ? maxStr : s.substring(left + 1, right);
    }
    return maxStr;
  }
}

时间复杂度

数组O(n)*每次扩展的时间O(n) = O(n^2)

空间复杂度

额外空间left、right、maxStr，常数级别O(1)