[leetcode] Longest Palindromic Substring *

 1 /*
 2  * DP
 3  *
 4  * d[i][j] represents the length of longest Palindromic
 5  *  substring of s[i...j].
 6  *
 7  *            |- j-i+1  (s[i] == s[j] && s[i+1...j-1] is Palindrome)
 8  *  d[i][j] = |
 9  *            |- max{ d[i+1][j], d[i][j-1] }
10  *
11  *  Note: use circular array.
12  */
13 
14 #include <string>
15 #include <iostream>
16 using namespace std;
17 
18 class Solution {
19 public:
20     string longestPalindrome(string s) {
21         // Start typing your C/C++ solution below
22         // DO NOT write int main() function
23         int len = s.length();
24 
25         int d[3][1000];
26         int st[3][1000];
27         for(int i=0; i<len; i++){
28             d[1][i] = 1;
29             st[1][i] = i;
30         }
31 
32         int idx2 = 2, idx1 = 1, idx0 = 0;
33         // DP
34         for(int l=2; l<=len; l++){
35             for(int i=0; i<=len-l; i++){
36                 if(s[i] == s[i+l-1] && (l == 2 || d[idx0][i+1] == l-2)){
37                     d[idx2][i] = l;
38                     st[idx2][i] = i;
39                 }
40                 else if(d[idx1][i+1] > d[idx1][i]){
41                     d[idx2][i] = d[idx1][i+1];
42                     st[idx2][i] = st[idx1][i+1];
43                 }
44                 else{
45                     d[idx2][i] = d[idx1][i];
46                     st[idx2][i] = st[idx1][i];
47                 }
48             }
49             idx2 = (idx2 + 1) % 3;
50             idx1 = (idx1 + 1) % 3;
51             idx0 = (idx0 + 1) % 3;
52 
53         }
54 
55         s[st[idx1][0]+d[idx1][0]] = 0;
56         return &s[st[idx1][0]];
57     }
58 };
59 
60 
61 int main(){
62     string s = "abccbd";
63 
64     cout << (new Solution())->longestPalindrome(s) << endl;
65 
66     return 0;
67 }