1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 13, 2014
4+ Problem: Longest Palindromic Substring
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/longest-palindromic-substring/
7+ Notes:
8+ Given a string S, find the longest palindromic substring in S.
9+ You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
10+
11+ Solution: 1. Time O(n^2), Space O(n^2)
12+ 2. Time O(n^2), Space O(n)
13+ 3. Time O(n^2), Space O(1) (actually much more efficient than 1 & 2)
14+ 4. Time O(n), Space O(n) (Manacher's Algorithm)
15+ */
16+ public class Solution {
17+ public String longestPalindrome_1 (String s ) {
18+ int n =s .length ();
19+ boolean [][]dp =new boolean [n ][n ];
20+ int idx =0 ,maxLen =0 ;
21+ for (int k =0 ;k <n ; ++k ) {
22+ for (int i =0 ;i +k <n ; ++i ) {
23+ if (k ==0 ||k ==1 )dp [i ][i +k ] = (s .charAt (i ) ==s .charAt (i +k ));
24+ else dp [i ][i +k ] = (s .charAt (i ) ==s .charAt (i +k )) ?dp [i +1 ][i +k -1 ] :false ;
25+ if (dp [i ][i +k ] ==true && (k +1 ) >maxLen ) {
26+ idx =i ;maxLen =k +1 ;
27+ }
28+ }
29+ }
30+ return s .substring (idx ,idx +maxLen );
31+ }
32+ public String longestPalindrome_2 (String s ) {
33+ int n =s .length ();
34+ boolean [][]dp =new boolean [2 ][n ];
35+ int idx =0 ,maxLen =0 ;
36+ int cur =1 ,last =0 ;
37+ for (int i =0 ;i <n ; ++i ) {
38+ cur =cur +last - (last =cur );
39+ for (int j =i ;j >=0 ; --j ) {
40+ if (j ==i ||j ==i -1 )
41+ dp [cur ][j ] = (s .charAt (i ) ==s .charAt (j ));
42+ else dp [cur ][j ] = (s .charAt (i ) ==s .charAt (j )) &&dp [last ][j +1 ];
43+ if (dp [cur ][j ] && (i -j +1 ) >maxLen ) {
44+ idx =j ;maxLen =i -j +1 ;
45+ }
46+ }
47+ }
48+ return s .substring (idx ,idx +maxLen );
49+ }
50+ public String longestPalindrome_3 (String s ) {
51+ int n =s .length ();
52+ int idx =0 ,maxLen =0 ;
53+ for (int i =0 ;i <n ; ++i ) {
54+ for (int j =0 ;j <=1 ; ++j ) {
55+ boolean isP =true ;
56+ for (int k =0 ;i -k >=0 &&i +j +k <n &&isP ; ++k ) {
57+ isP = (s .charAt (i -k ) ==s .charAt (i +j +k ));
58+ if (isP && (j +1 +k *2 ) >maxLen ) {
59+ idx =i -k ;maxLen =j +1 +k *2 ;
60+ }
61+ }
62+ }
63+ }
64+ return s .substring (idx ,idx +maxLen );
65+ }
66+ public String longestPalindrome_4 (String s ) {
67+ int n =s .length ();
68+ int idx =0 ,maxLen =0 ;
69+ StringBuffer sb =new StringBuffer ();
70+ sb .append ('^' );
71+ for (int i =0 ;i <n ; ++i ) {
72+ sb .append ('#' );
73+ sb .append (s .charAt (i ));
74+ }
75+ sb .append ("#$" );
76+ n =2 *n +2 ;
77+ int mx =0 ,id =0 ;
78+ int []p =new int [n ];
79+ Arrays .fill (p ,0 );
80+ for (int i =1 ;i <n -1 ; ++i ) {
81+ p [i ] = (mx >i ) ?Math .min (p [2 *id -i ],mx -i ):0 ;
82+ while (sb .charAt (i +1 +p [i ]) ==sb .charAt (i -1 -p [i ])) ++p [i ];
83+ if (i +p [i ] >mx ) {
84+ id =i ;mx =i +p [i ];
85+ }
86+ if (p [i ] >maxLen ) {
87+ idx =i ;maxLen =p [i ];
88+ }
89+ }
90+ idx = (idx -maxLen -1 ) /2 ;
91+ return s .substring (idx ,idx +maxLen );
92+ }
93+ }
