leetcode-cpp/0005-longest-palindromic-substring.cpp at main · j414j/leetcode-cpp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<string>
#include<vector>

using namespace std;

//class Solution {
//public:
//  string longestPalindrome(string s) {
//    int n = s.size();
//
//    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
//    int len = 1;
//    int maxi = 0;
//
//    for (int i = n - 1; i >= 0; i--) {
//      dp[i][i] = 1;
//      for (int j = i + 1; j < n; j++) {
//        if (s[i] == s[j]) {
//          // if the inner string is not already a palindrome then it can
//          // be a valid palindrome only if i and j are consecutive.
//          // So in the string "abbca" dp[1][2] should be 2
//          // but dp[0][4] should not be 2, rather it should be 0;
//          if (dp[i + 1][j - 1] == 0 && i != j - 1) continue;
//          dp[i][j] = 2 + dp[i + 1][j - 1];
//          if (dp[i][j] > len) {
//            len = dp[i][j];
//            maxi = j;
//          }
//        }
//      }
//    }
//    return s.substr(maxi - len + 1, len);
//  }
//};

// space optimised tabulation
class Solution {
public:
  string longestPalindrome(const string &s) {
    int n = s.size();

    vector<int> prev(n+1, 0);
    vector<int> curr(n+1, 0);
    int len = 1;
    int maxi = 0;

    for (int i=n-1;i>=0;i--) {
      curr[i] = 1;
      for (int j=i+1;j<n;j++) {
        if (s[i] == s[j] && !(prev[j-1] == 0 && i != j-1)) {
          curr[j] = 2 + prev[j-1];
          if (curr[j] > len) {
            len = curr[j];
            maxi = j;
          }
        } else curr[j] = 0;
      }
      prev = curr;
    }
    return s.substr(maxi-len+1, len);
  }
};

// TODO: Optimise this with Manacher's Algortihm