LeetCode Longest Palindromic Substring

Description

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

The original problem is here.

The original code is here.

My Solution

I solve this problem in C++, as below:

/*
*Longest Palindromic Substring 
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
*/
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        if(len <= 1)
            return s;
        string str;
        int maxLen = 0;
        bool p[1000][1000] = {0};
        
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                if(s[i] == s[j] && (j-i<=2 || p[i+1][j-1])){
                    p[i][j] = true;
                    int sublen = j - i +1;
                    if(sublen > maxLen){
                        str = s.substr(i,sublen);
                        maxLen = sublen;
                    }
                }
                else
                    p[i][j] = false;
            }
        }
        return str;
    }
};

int main(){
    string str("aaabaaaa");
    Solution s;
    cout<<"str="<<str<<endl;
    //string new_str = s.inverse(str);
    //cout<<"new str="<<new_str<<endl;
    //cout<<"isPalindrome="<<s.isPalindrome(str);
    string substr = s.longestPalindrome(str);
    cout<<"substr="<<substr<<endl;
}

Note

To solve the problem, dynamic program is used. P[i][j] labels whether the substr(i,j) is palindrome or not.