# Cannot use recursion + memorization (Memory Limit Exceeded)

• 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;
``````

• 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?

• 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);
}
};
``````

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