Cannot use recursion + memorization (Memory Limit Exceeded)


  • 0

    Same idea as the popular DP + lookup table method, but got MLE for extremely long input s.

    I know the call stack is too long ... I just like the recursive way to organize thoughts. That's all...

        int numDecodings(string s) {
            if (s.empty()) return 0;
            memo = vector<int>(s.size(), -1);
            return ways(s);
        }
        
        long ways(string s, int i = 0) {
            if (i == s.size()) return 1;
            if (i > s.size()) return 0;
            if (memo[i] >= 0) return memo[i];
            if (s[i] == '0') return 0;
            
            long res = 0;
            if (s[i] == '*') { 
                res = (9*ways(s, i+1))%MOD;
                if (i+1 < s.size()) {
                    if (s[i+1] == '*') (res += 15L*ways(s, i+2)) %= MOD;
                    else if (s[i+1] - '6' > 0) (res += ways(s, i+2)) %= MOD;
                    else (res += 2L*ways(s, i+2)) %= MOD;
                }
            }
            else {
                res = ways(s, i+1);
                if (i+1 < s.size()) {
                    if (s[i] == '1') {
                        if (s[i+1] == '*') (res += 9L*ways(s, i+2)) %= MOD;
                        else (res += ways(s, i+2)) %= MOD;
                    }
                    else if (s[i] == '2') {
                        if (s[i+1] == '*') (res += 6L*ways(s, i+2)) %= MOD;
                        else if (s[i+1] - '7' < 0) (res += ways(s, i+2)) %= MOD;
                    }
                }            
            }
            return memo[i] = res;
            
        }
        
        const int MOD = 1000000007;
        vector<int> memo;
    

  • 0
    J

    I believe the Java stack size in leetcode compiler is too small, The biggest length of input string is 10,000, so the stack size will not be bigger than 1M(1w*100); Can @administrators explains what is the Java stack size in Leetcode?


Log in to reply
 

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