5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

 1 class Solution {
 2     public String longestPalindrome(String s) {
 3         int n = s.length();
 4         if (n == 0) return "";
 5         boolean [][]flag = new boolean[n][n];
 6         for (int i = 0; i < n; ++i) {
 7             flag[i][0] = true;
 8         }
 9         
10         for (int len = 2; len <= n; ++len ) {
11             for (int i = 0; i + len - 1 < n; ++i) {
12                 
13                 if (s.charAt(i) != s.charAt(i + len - 1)) continue;
14                 if (len - 3 == -1 || flag[i + 1][len - 3]) {
15                     flag[i][len - 1] = true;
16                 }
17             }
18         }
19         
20         for (int len = n; len >= 0; --len ) {
21             for (int i = 0; i + len - 1 < n; ++i) {
22                 if (flag[i][len - 1]) return s.substring(i, i + len);
23             }
24         }
25         return "";
26     }
27 }

View Code

 1 class Solution {
 2     public String preProcess(String s) {
 3         int n = s.length();
 4         if (n == 0) {
 5             return "^$";
 6         }
 7         String ret = "^";
 8         for (int i = 0; i < n; ++i) {
 9             ret += "#" +  s.charAt(i);
10         }
11         ret += "#$";
12         return ret;
13         
14     }
15     public String longestPalindrome(String s) {
16         int n = s.length();
17         if (n == 0) return "";
18         String t = preProcess(s);
19         
20         n = t.length();
21         int c = 0, r = 0;
22         int []p = new int[n];
23         for (int i = 1; i < n - 1; ++i) {
24             int i_mirror = 2 * c - i;
25             if (r > i) {
26                 p[i] = Math.min(p[i_mirror], r - i);
27                 
28             } else {
29                 p[i] = 0;
30             }
31             
32             while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) {
33                 p[i]++;
34             
35             }
36             
37             
38             if (i + p[i] - 1 > r) {
39                 r = i + p[i] - 1;
40                 c = i;
41             }
42         }
43         
44         int maxlen = 0;
45         int start = 1;
46         for (int i = 2; i < n; ++i) {
47             if (p[i] > maxlen) {
48                 maxlen = p[i];
49                 start = (i - p[i]) / 2;
50             }
51         }
52         
53         return s.substring(start, start + maxlen);
54         
55         
56         
57         
58         
59     }
60 }

View Code