1212 2. Time O(n^2), Space O(n)
1313 3. Time O(n^2), Space O(1) (actually much more efficient than 1 & 2)
1414 4. Time O(n), Space O(n) (Manacher's Algorithm)
15+ 5. Time O(n), Smaller Space than solution 4. (Manacher's Algorithm)
1516 */
17+
1618public class Solution {
1719public String longestPalindrome_1 (String s ) {
1820int n =s .length ();
@@ -73,12 +75,12 @@ public String longestPalindrome_4(String s) {
7375sb .append (s .charAt (i ));
7476 }
7577sb .append ("#$" );
76- n =2 *n +2 ;
78+ n =2 *n +3 ;
7779int mx =0 ,id =0 ;
7880int []p =new int [n ];
7981Arrays .fill (p ,0 );
8082for (int i =1 ;i <n -1 ; ++i ) {
81- p [i ] = (mx >i ) ?Math .min (p [2 *id -i ],mx -i ):0 ;
83+ p [i ] = (mx >i ) ?Math .min (p [2 *id -i ],mx -i )0 ;
8284while (sb .charAt (i +1 +p [i ]) ==sb .charAt (i -1 -p [i ])) ++p [i ];
8385if (i +p [i ] >mx ) {
8486id =i ;mx =i +p [i ];
@@ -90,4 +92,30 @@ public String longestPalindrome_4(String s) {
9092idx = (idx -maxLen -1 ) /2 ;
9193return s .substring (idx ,idx +maxLen );
9294 }
95+ public String longestPalindrome_5 (String s ) {
96+ int n =s .length ();
97+ int idx =0 ,maxLen =0 ;
98+ int mx =0 ,id =0 ;
99+ int []p =new int [2 *n +1 ];
100+ Arrays .fill (p ,0 );
101+ for (int i =0 ;i <2 *n +1 ; ++i ) {
102+ p [i ] = (mx >i ) ?Math .min (p [2 *id -i ],mx -i ) :0 ;
103+ int left =i -1 -p [i ],right =i +1 +p [i ];
104+ while (left >=0 &&right <=2 *n ) {
105+ if (left %2 ==0 ||s .charAt (left /2 ) ==s .charAt (right /2 )) {
106+ ++p [i ];
107+ }else break ;
108+ --left ;
109+ ++right ;
110+ }
111+ if (i +p [i ] >mx ) {
112+ id =i ;mx =i +p [i ];
113+ }
114+ if (p [i ] >maxLen ) {
115+ idx =i ;maxLen =p [i ];
116+ }
117+ }
118+ idx = (idx -maxLen ) /2 ;
119+ return s .substring (idx ,idx +maxLen );
120+ }
93121}
