Fully Explained C++ Solution

  • 0

    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!

Log in to reply

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