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:
- dp[i]: The number of ways to decode a substring in S between index 0..(i-1)
- 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 as it contains ways to decode for S. dp is initialized to 1 as well to be used by dp iteration and makes it easier. The code is as below:
def numDecodings(self, s): if not s or s == "0": return 0 dp =  * (len(s) + 1) dp = dp = 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]