Help Leetcode December Challenge

help
, ,
1

CAN ANYONE HELP ME WITH THIS PROBLEM.

2

:- i have used recursion + Memorization
this is my solution

int solve(char ch[],int pos,int n,int dp[]){
if(pos >= n){
return 1;
}
int d = ch[pos]-‘0’;
if(d == 0)
return 0;
if(dp[pos] != -1)
return dp[pos];
int ans = 0 ;
int no = 0;
if(pos+1 != n){
no = Integer.parseInt(d+""+(ch[pos+1]-‘0’));
}
if(no >=1 && no <= 26)
ans +=solve(ch,pos+2,n,dp);
ans+=solve(ch,pos+1,n,dp);
return dp[pos] = ans;
}
public int numDecodings(String s) {
int n = s.length();
if(s.charAt(0) == ‘0’)
return 0;
if(n == 1)
return 1;
int dp[] = new int[n];
Arrays.fill(dp,-1);
return solve(s.toCharArray(),0,n,dp);
}

so basically what i did is that for every index i we have to choice two choice depending on the condition. )

  1. if ch[i] != 0 then we choose that character and recursion solve(i+1)
    2)if i +1 != n (‘0’ based index) && 1 <= DIGIT(ch[i],ch[i+1]) <= 26 then we choose two digit at ones ans call solve(i+2)
    we will return sum of both of the choice.

i hope you get it… asked if you still have doubt.

3

Bro I haven’t studied dp yet. Can you solve it without it.
But still I’ll study your code and try to understand.