Using DP. Getting Runtime Error on input "aaaaaaaaaaaaa......"


  • 0
    S

    Hi.
    I am using bottom up dp with extra memory to calculate the validity of given string.
    My code first initializes the base case values and then do further calculation in bottom up format.

    However, I am still getting Runtime error on this pretty long input.
    Thanks for any help in advance.

    class Solution {
    public:
        bool isMatch(const char *s, const char *p) {
            string ss(s);
            string pp(p);
            int m = ss.size();
            int n = pp.size();
        
            if (s == NULL || p == NULL)
                return false;
        
            bool OPT[m+1][n+1];
            OPT[0][0] = true;
        
            for (int i = 1; i <= m; i++)
                OPT[i][0] = false;
    
            for (int j = 1; j <= n; j++)
                OPT[0][j] = (pp[j-1] == '*') && OPT[0][j-1];
        
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++)
                {
                    OPT[i][j] = ( (OPT[i-1][j-1]) && equals(ss, pp, i-1, j-1) ) ||  ( (OPT[i-1][j]) && (pp[j-1] == '*') )
                              ||  ((OPT[i][j-1]) && (pp[j-2] == '*') && (equals(ss, pp, i-1, j-1)));
                }
            return OPT[m][n];
        }
        
        bool equals(string s, string p, int si, int pi) {
            return (s[si] == p[pi] || p[pi] == '?');
        }
    };

  • 3
    L

    bool OPT[m+1][n+1]

    size of the mentioned test case : s.size()= 32316, p.size(): 32318

    This means a memory location of 32317*32319 bytes is required which is way past the maximum limit allowed for continuous memory allocation with an array structure.


  • 0
    U

    Your explanation does help me understand some problems I have met, but where do you get these numbers like 32317*32319? Would you please tell me where I can learn things about memory allocation?


Log in to reply
 

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