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[i,j] =
字符串区间[i,j]是否为palindrome.
首先找个例子，比如S="abccb",
S= a b c c b
Index =
0 1 2 3 4
P[0,0] =1 //each
char is a palindrome
P[0,1] =S[0] == S[1] , P[1,1]
=1
P[0,2] = S[0] == S[2] && P[1,1], P[1,2] = S[1]
== S[2] , P[2,2] = 1
P[0,3] = S[0] == S[3] && P[1,2],
P[1,3] = S[1] == S[3] && P[2,2] , P[2,3] =S[2] ==S[3], P[3,3]=1
......................
由此就可以推导出规律
P[i,j]
= 1 if i ==j
= S[i]
==S[j] if j = i+1
=
S[i] == S[j] && P[i+1][j-1] if j>i+1
1 public class Solution { 2 3 public String longestPalindrome(String s) { 4 int len = s.length(); 5 boolean[][] p = new boolean[len][len]; 6 int maxL = 0, start=0, end = 0; 7 8 for(int i = 0; i < len; i++){ 9 for(int j = 0; j<i; j++){ 10 // i - j < 2 是两个字符中间只隔一个字符 11 if((s.charAt(j) == s.charAt(i)) && (i-j<2 || p[j+1][i-1])){ 12 p[j][i] = true; 13 } 14 if(p[j][i] && maxL<(i-j+1)){ 15 maxL = i-j+1; 16 // star 和 end 记录最长字符的index 17 start = j; 18 end = i; 19 } 20 } 21 // 每一个字符本事都是 palindrome 22 p[i][i] =true; 23 } 24 return s.substring(start, end+1); 25 } 26 }
注意： 只有当P[j][i] == true时 才比较maxL
[Leetcode]-- Longest Palindromic Substring
原文：http://www.cnblogs.com/RazerLu/p/3540023.html
