aboutsummaryrefslogtreecommitdiff
path: root/longest_palindromic_substr.cpp
blob: 4ecba2585f42ddd478599536c5c600ea90c19774 (plain)
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
#include "leetcode.h"

class Solution {
public:
  string longestPalindrome(string s) {
    if (s.size() == 0)
      return "";
    int i = 0, j = 0, n = s.size();
    bool p[n][n] = {false};
    for (int x = 0; x < n; x++) {
      p[x][x] = true;
      if (x == n - 1)
        break;
      p[x][x + 1] = (s[x] == s[x + 1]);
    }
    for (int i = n - 3; i >= 0; --i)
      for (int j = i + 2; j < n; ++j)
        p[i][j] = (p[i + 1][j - 1] && s[i] == s[j]);
    int max = 0;
    string ans = "";
    for (int i = 0; i < n; i++)
      for (int j = i; j < n; j++)
        if (p[i][j] == true && j - i + 1 > max) {
          max = j - i + 1;
          ans = s.substr(i, j - i + 1);
        }
    return ans;
  }
};

int main() {
  Solution obj;
  string s = "babad";
  cout << obj.longestPalindrome(s);
}