Cannot use recursion + memorization (Memory Limit Exceeded)


  • 1

    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?


  • 1
    D

    I got an almost similar solution to pass the judge by making it evaluate the memoized result incrementally (in steps of 1000).

    class Solution {
        vector<int> dp;
        const int MOD = 1000000007;
        long decodeWays(string const &s, int start) {
            if (start == s.size()) return 1;
            if (dp[start] != -1) return dp[start];
            const char ch = s[start];
            long ways = 0;
            if (ch == '0') {
                return dp[start] = 0;
            } else if (ch == '1') {
                ways = decodeWays(s, start + 1);
                if (start + 1 < s.size()) {
                    const long mul = s[start + 1] == '*' ? 9L : 1L;
                    ways += ((mul * decodeWays(s, start + 2)) % MOD);
                }
            } else if (ch == '2') {
                ways = decodeWays(s, start + 1);
                if (start + 1 < s.size() && (s[start + 1] == '*' || s[start + 1] < '7')) {
                    const long mul = s[start + 1] == '*' ? 6L : 1L;
                    ways += ((mul * decodeWays(s, start + 2)) % MOD);
                }
            } else if (ch == '*') {
                ways = (9L * decodeWays(s, start + 1)) % MOD;
                if (start + 1 < s.size()) {
                    const char next = s[start + 1];
                    const long mul = (next == '*') ? 15L : (next < '7' ? 2L : 1L);
                    ways += ((mul * decodeWays(s, start + 2)) % MOD);
                }
            } else {
                ways = decodeWays(s, start + 1);
            }
            ways %= MOD;
            return dp[start] = ways;
        }
    public:
        int numDecodings(string s) {
            dp.clear();
            dp.resize(s.size(), -1);
            if (s.size() > 1000) {
                int idx = s.size() - 1000;
                while (idx >= 0) {
                    decodeWays(s, idx);
                    if (idx == 0) {
                        idx = -1;
                    } else {
                        idx -= 1000;
                        idx = std::max(idx, 0);
                    }
                }
            }
            return decodeWays(s, 0);
        }
    };
    

Log in to reply
 

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