Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
最难想的地方：P代表一个表，比较难想的就是P表的下标i和j代表原字符串中的两个前后下标s[i]和s[j]的位置。
如果P[i,j]为真，当且仅当si-1,si-2...sj-1,sj这一个子串都为palindrome。例如：s[] = skrdjdre那么P[2][6] = true，因为s[2]=r=s[6],且djd为回文。
不明白，可以看下表，动手填一填，未填出的都初始化为false,其中t代表填写true：
基本思路是外层循环i从后往前扫，内层循环j从i当前字符扫到结尾处。过程中使用的历史信息是从i+1到n之间的任意子串是否是回文已经被记录下来，所以不用重新判断，只需要比较一下头尾字符即可。这种方法使用两层循环，时间复杂度是O(n^2)。而空间上因为需要记录任意子串是否为回文，需要O(n^2)的空间，
public class Solution { public String longestPalindrome(String s) { if(s == null || s.length()==0) return ""; boolean[][] palin = new boolean[s.length()][s.length()]; String res = ""; int maxLen = 0; for(int i=s.length()-1;i>=0;i--) { for(int j=i;j<s.length();j++) { if(s.charAt(i)==s.charAt(j) && (j-i<=2 || palin[i+1][j-1])) { palin[i][j] = true; if(maxLen<j-i+1) { maxLen=j-i+1; res = s.substring(i,j+1); } } } } return res; } }
public class Solution {//Time Limit Exceeded
public String longestPalindrome(String s) { if(s.length() == 0) return ""; int n = s.length(); String longestPalindrome = null; int max = -1; for(int i = 0 ; i< n ; i++){ for(int j = i+1 ; j<n ; j++){ String cur = s.substring(i,j+1); if(isPalindrome(cur)){ if(cur.length() > max){ max = cur.length(); longestPalindrome = cur; } } } } return longestPalindrome; } public static boolean isPalindrome(String s) { for (int i = 0; i < s.length() - 1; i++) { if (s.charAt(i) != s.charAt(s.length() - 1 - i)) { return false; } } return true; } }
public class Solution { public String longestPalindrome(String s) { // Start typing your Java solution below // DO NOT write main() function int n = s.length(); String result =""; for(int i = 0 ; i< 2*n -1;i++){ int left = i , right = i/2+1; if(i%2 ==0){ left = i/2-1; } else{ left = i/2; } while(left>=0&&right<n&&s.charAt(left) == s.charAt(right)){ left--; right++; } if(right - left -1 > result.length()){ result = s.substring(left+1,right); } } return result; } }