Longest palindromic substring -- leetcode

Question:
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.
Answer:
//Example:
//s="fgabcdcbaddeee"
//return="abcdcba"

method 1: Brute Force: Time O(n^3), Space:O(n)

class Solution {
public:
    string longestPalindrome(string s) {
     
        int len = s.length();
        int max = 1, startI=0;    //if cannot find a palindrome whose len > 1, then return s[0] for default.
        int flag[len];
     
        for(int i=0;i<len;++i){
            flag[i] = -1;
        }
     
        for(int i=0; i<len; ++i){      //for start index = i

            for(int j=len-1;j>=i+max-1;--j){
             
                if(isPalindrome(s.substr(i,j-i+1))){//find the longest palindromic substring (i,j) for substr starting from i.
                    flag[i] = j;
                    break;
                }
            }
            //have traversed all substr(i,j) for substring whose starting index = i.
            if(flag[i]-i+1 > max){
                max = flag[i]-i+1;
                startI = i;
            }
        }
        return s.substr(startI,flag[startI]-startI+1);
    }
 
    bool isPalindrome(string s){
        int len=s.length();
        for(int i=0;i<len/2;++i){
            if(s[i]!=s[len-i-1]){
                return false;
            }
        }
        return true;
    }
};




method 2: DP : Time O(n^2), Space O(n^2)

DP公式：

dp[i][j] = ( s[i] == s[j] && (dp[i+1][j-1]>0 || j-i <=1) )

             =  1,   if i==j

Code：

string longestPalindrome(string s) {
     
        int len = s.length();
        int maxLen = 1, startI=0;  
                    //if cannot find a palindrome whose len > 1, then return s[0] for default.
        int dp[len][len];

        memset(dp,0,len*len*sizeof(int));
     
        for(int j=0;j<len;++j){         //i<j,右上三角矩阵
         
            for(int i=0; i<j;++i){
             
                if(s[i]==s[j] && (dp[i+1][j-1]>0 || j-i <=1)){       //dp[i][j] >0 ,is palindrome = len(s(i,j))
                    dp[i][j] = j-i+1;
                    if(j-i+1 > maxLen){
                        maxLen = j-i+1;
                        startI = i;
                    }
                }
            }
            dp[j][j] = 1;
        }
        return s.substr(startI, maxLen);
    }