Memory Limit Exceeded: Longest Palindromic Substring


  • 1
    K

    Can anyone tell me why this code gave Memory limit exceeded ?

    class Solution {
    public:
        string longestPalindrome(string s) {
            if(s.length() < 2) return s;
           
            // dp[i][j] denotes longest palindromic substring length from i to j
            vector<vector<int> >  dp(s.length(), vector<int>(s.length(), 0));
            int n = s.length();
            int start = 0, end = 0, Max = 1;
            for(int i = n - 1; i >= 0; --i) {
                dp[i][i] = 1;
                for(int j = i + 1; j < n; ++j) {
                    dp[i][j] = (s[i] == s[j] and (j - i < 3 or dp[i + 1][j - 1] == j - 1 - i))
                               ? dp[i + 1][j - 1] + 2
                               : max(dp[i][j - 1], dp[i + 1][j]);
                    if(dp[i][j] > Max) {
                        Max = dp[i][j];
                        start = i, end = j;
                    }
                }
            }
            return s.substr(start, end - start + 1);
        }
    };

  • 0
    R

    You were asking a question in a wrong section.


  • 0
    K

    Sorry, now I put it in right section!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.