We take an additional array ** dp** of same size as of the string, let say

**N**.

Here the

**ith**element of array i.e.

**dp[i]**will represent the number of possible decodings using the first

**i**elements of input string. So,Obviously the answer would be

**dp[N-1]**.

The Algorithm includes basically only two steps:

**1.**If the

**ith**character is a valid one digit number i.e.

**1<=s[i]<=9**(only check if

**s[i]!=0**), then

**.**

*dp[i]=dp[i-1]*This is because we can append the character corresponding to the

**ith**digit,to the right of all the possible decodings that have been done yet, so we will get only as many number of decodings as using

**i-1**elements of the string(i.e.

**).**

*dp[i-1]***2.** If the **ith** character and the **(i-1)th** makes up a valid two digit number i.e. between **(10 and 26)** , then ** dp[i]+=dp[i-2]**.

This is because we can append character for this two digit number, to the right of all the decodings possible using first

**(i-2)**elements of the string, since we already used

**(i-1)th and ith**element to make this two digit number.

For more detailed explanation, you can check the following code.

Thanks and Good Luck!