```
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
def util(x):
"""
x - an input string of either one or two characters
returns a number of ways to represent a string x
"""
if x.isdigit() == False:
return 0 # if string is non digit, we can't decode it
else:
d = int(x)
if d == 0 or x[0] == '0': # if digit is either 0 or x begins with '0' then cant decode it
return 0
if 1 <= d <= 26:
# strings '1','2'....'26'
return 1
else:
# anything above '26', can't decode it
return 0
if s == None or len(s) == 0:
return 0
n = len(s)
func = [ 0 for i in range(n)] # func[i] = number of ways to decode a string s[0:i+1] or s0s1s2....si character string
func[0] = util(s[0]) # how many ways can you decode first character
if n > 1: # if at least 2 chars are present
func[1] = func[0]*util(s[1]) + util(s[0:2]) # how many ways can you decode first couple
for i in range(2,n):
# formula is based on observation that number of ways to decode
# numberOfWaysToDecode(s[0:i+1]) = numberOfWaysToDecode(s[0:i]) * numberOfWaysToDecode(s[i]) + numberOfWaysToDecode(s[0:i-2]) * numberOfWaysToDecode(s[i-1:i+1])
# Why above formula?
# Assume we have a string (s0, s1, s2....si-1) and now we append si to it to form (s0,s1,s2...si-1,si)
# Then si can be on its own in which case partition decoding as (s0,s1,s2...si-1) | si --- first term of formula
# AND si can be with its preceeding char in which case partition decoding as (s0,s1,s2...si-2) | (si-1,si) --- second term of formula
func[i] = func[i-1] * util(s[i]) + func[i-2] * util(s[i-1:i+1])
return func[n-1] # number of ways to decode s[0:n]
```