Getting TLE in Question on Longest palindrome substring.

Правка en4, от _WATerror_AK, 2021-08-03 13:37:20

Can anyone help me out with my code to optimise this code.

Question Link-https://leetcode.com/problems/longest-palindromic-substring/

Submission Link-Submission

include<bits/stdc++.h>

using namespace std; int dp[1001][1001]={-1}; bool is_palindrome(string s){ int i=0,j=s.length()-1; while(i<=j){ if(s[i]!=s[j]) return 0; i++,j--; } return 1; } int solve(string s,int i,int j){ if(i==j) return dp[i][j]=1; if(i>j) return dp[i][j]=0;

if(dp[i][j]!=-1) return dp[i][j];

    if(s[i]==s[j]){
        if(solve(s,i+1,j-1)==(j-i-1)) return dp[i][j]=j-i+1;
        else{
            return dp[i][j]=max({solve(s,i,j-1),solve(s,i+1,j)});
        }
    }

    return dp[i][j]=max({solve(s,i,j-1),solve(s,i+1,j)});

}

string longestPalindrome(string S) {

memset(dp,-1,sizeof(dp));
int cnt=solve(S,0,S.length()-1),n=S.length();

for(int i=0;i<=n-cnt;i++){
    if(is_palindrome(S.substr(i,cnt))){
        return S.substr(i,cnt);
    }
}
return S;

} int main(){ int tc; cin >> tc; while(tc--){ string s; cin>>s;

cout<<longestPalindrome(s)<<"\n";
}
return 0;

}

Теги # 2d dp, longest palindorme

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский _WATerror_AK 2021-08-03 13:48:35 38 Tiny change: 'tcode.com/submissions/detail/532338690/)\n' -> 'tcode.com/playground/gWN5kxkZ)\n'
en6 Английский _WATerror_AK 2021-08-03 13:41:07 17
en5 Английский _WATerror_AK 2021-08-03 13:39:08 1141
en4 Английский _WATerror_AK 2021-08-03 13:37:20 80
en3 Английский _WATerror_AK 2021-08-03 13:34:06 274
en2 Английский _WATerror_AK 2021-08-03 13:32:10 220
en1 Английский _WATerror_AK 2021-08-03 13:30:42 1331 Initial revision (published)