给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2：
输入: “cbbd” 输出: “bb”
思路：中心扩散法，即分奇数和偶数扩展，每次扩散都比较最长回文子串，和记录最大值。 for(int i = 0;i<len;i++) { 从i开始的奇数扩散 从i,i+1的偶数扩散 }
class Solution { public String longestPalindrome(String s) { int len = s.length(); if (len == 0) { return ""; } int longestPalindrome = 1; String longestPalindromeStr = s.substring(0, 1); for (int i = 0; i < len; i++) { String palindromeOdd = centerSpread(s, len, i, i); String palindromeEven = centerSpread(s, len, i, i + 1); String maxLen = palindromeOdd.length() > palindromeEven.length() ? palindromeOdd : palindromeEven; if (maxLen.length() > longestPalindrome) { longestPalindrome = maxLen.length(); longestPalindromeStr = maxLen; } } return longestPalindromeStr; } private String centerSpread(String s, int len, int left, int right) { int l = left; int r = right; while (l >= 0 && r < len && s.charAt(l) == s.charAt(r)) { l--; r++; } // 这里要特别小心，跳出 while 循环的时候，是第 1 个满足 s.charAt(l) != s.charAt(r) 的时候 // 所以，不能取 l，不能取 r return s.substring(l + 1, r); } }