# Accepted Python DP Solution w/ Explanation

• The question might be simple for many, however it took me quite some time to find a clean and easy way to understand and implement the solution. Thought to share with those that are new like me.

It's a typical DP question, with additional checks to consider:

1. dp[i]: The number of ways to decode a substring in S between index 0..(i-1)
2. dp[i] is the sum of dp[i-1] if
S[i] is a valid decode, i.e. '1' <= S[i] <= '9', and dp[i-2] if substring S[i-1]S[i] is a valid decode, i.e. '10' <= S[i-1]S[i] <= '26'

After handling special case, dp[1] = 1 as it contains ways to decode for S[0]. dp[0] is initialized to 1 as well to be used by dp[2] iteration and makes it easier. The code is as below:

``````def numDecodings(self, s):

if not s or s[0] == "0": return 0

dp = [0] * (len(s) + 1)
dp[0] = dp[1] = 1
for i, c in enumerate(s[1:], 1):
if c >= "1" and c <= "9":
dp[i+1] = dp[i]
if s[i-1:i+1] and s[i-1:i+1] <= "26" and s[i-1:i+1] >= "10" :
dp[i+1] += dp[i-1]

return dp[-1]

``````

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