hot100 5.最长回文子串

一、方法一：中心扩散法。

1.思路：由于回文串一定是对称的，所以可以每次循环选择一个中心，进行左右扩展，判断左右字符是否相等即可。

2.由于存在长度为奇数的字符串和长度为偶数的字符串，所以我们需要从一个字符开始扩展，或者从两个字符之间开始扩展，所以总共有n + n - 1个中心。

3.复杂度分析：

（1）时间复杂度：O(n^2)。

（2）空间复杂度：O(1)。

附代码：

class Solution { public String longestPalindrome(String s) { if(s == null || s.length() == 0){ return ""; } int start = 0,end = 0; // 记录最长回文子串的起始和结束位置 for(int i = 0;i < s.length();i++){ int len1 = expandAroundCenter(s,i,i); // 奇数长度扩展的字符串，以i为中心 int len2 = expandAroundCenter(s,i,i + 1); // 偶数长度扩展的字符串，以i和i + 1为中心 int len = Math.max(len1,len2); // 取两种情况的最大值 if(len > end - start)