中心扩展法，依次遍历每个字符。
class Solution { // // 思路1: DP。这种思路就是尝试所有可能的palin的长度, [0, len], 遍历左右的[i,j]组合，找出其中最长的回文串。 // public String longestPalindrome(String s) { // // corner // if (s == null || s.length() < 2) return s; // int sLen = s.length(), maxLen = 1; // String longest = null; // string的初始化可以为null // boolean[][] dp = new boolean[sLen][sLen]; // 判断i...j是不是回文 // for (int k = 0; k < sLen; k++) { // k --> possible palin len // for (int i = 0; i < sLen - k; i++) { // int j = i + k; // if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1] == true)) { // 二维矩阵其实只填满了右上部分 // dp[i][j] = true; // int currLen = j - i + 1; // 此时必定回文 // if (currLen > maxLen) { // maxLen = currLen; // longest = s.substring(i, j + 1); // } // } // } // } // return longest == null ? s.substring(0, 1) : longest; // } // 思路2: 从每个点开始，分别向左右拓展，看能获得的最长的回文串有多长。拓展的时候，要分两种情况：1.回文串是奇数（以当前字母为中心）；2.回文串是偶数（以当前字母和其右边/左边的字母为中心）。keep一个global max，每次拓展完成之后，就比较一下。 // time：不一定。如果是"aaaaaa"这样的，会有很多重复的visit(从左向右数，2n/2n-1/2n-2/...), 会达到n^2。如果是"abcde"这样的，直接就是O(n). int max = 0; // 回文串最小的长度是1（某字母本身） int start = 0; // maxPalin的起点 public String longestPalindrome(String s) { // corner case if (s == null || s.length() == 0) return ""; // if (s.length() == 1) return s; // extendPalin函数可以handle长度为1的情况 for (int i = 0; i < s.length(); i++) { extendPalin(s, i, i); extendPalin(s, i, i + 1); } return s.substring(start, start + max); // 用"起点+长度"来确定substring，更方便 } private void extendPalin(String s, int i, int j) { while (i >= 0 && i < s.length() && j >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) { // 这里不要写i-1和j+1，因为前面的判断条件只能保证i和j不越界。 i--; j++; } int currLen = j - i - 1; // (j - 1) - (i + 1) + 1, 循环终止前一轮的substring(i, j)才是我们想要的 if (currLen > max) { max = currLen; start = i + 1; } } } /* cbabc */动态规划，神奇的方法：
class Solution { public String longestPalindrome(String s) { int n = s.length(); String res = ""; boolean[][] dp = new boolean[n][n]; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]); if (dp[i][j] && (j - i + 1 > res.length())) { res = s.substring(i, j + 1); } } } return res; } }
