Https://leetcode.com/problems/decode-ways/

, ,
1

What is wrong in my code, using memoization recursive solution.

class Solution {
public:
int helper(string s,int n,vector &dp){
if(s[0] == ‘0’){
return dp[0] = 0;
}

    if(n == 0 || n == 1){
        dp[n] = 1;
    }
    if(dp[n]!= -1){
        return dp[n];
    }
    
    if(s[n-1] > '0'){
        dp[n] = helper(s,n-1,dp);
    }
        
    if((s[n-2] == '1') || (s[n-2] == '2' && s[n-1] < '7')){
        dp[n]+= helper(s,n-2,dp);
    }
    
    return dp[n];

}

int numDecodings(string s) {
    int n = s.size();
    vector<int> dp(n+1,-1);
    int ans = helper(s,n,dp);
    for(int i=0;i<n+1;i++){
        cout << dp[i] << " ";
    }
    return ans;
    
    
}

};

failing on test case - s = “12345609”;
when 0 is comes it fails.

2

AC code . You forgot to do dp[n]=0 after if (dp[n]!=-1)

3

please paste your code here, not able to see…

4

I am getting tle in memoization is there any optimiazation?

5

Code

6

thanks @dhruv788

1 Like