# Python solution with explanation

• ``````class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
# the number of decodings for s[0...k] (inclusive) is num[k]
# and it can be expressed by s[0...k-1] or s[0...k-2] depending on
# whether we choose to combine the last two characters
self.mod = 10 ** 9 + 7
self.memorytwo = {}
if not s or s[0] == '0':
return 0
n = len(s)
num = [0] * n;
if s[0] == '*':
num[0] = 9
else:
num[0] = 1
for k in range(1, n):
num[k] = 0
# not combine
if s[k] != '0':
if s[k] == '*':
num[k] = num[k - 1] * 9 % self.mod
else:
num[k] = num[k - 1]
# combine
t = self.numDecodingsOfTwo(s[k-1:k+1])
if t > 0:
if k == 1:
num[k] += t
else:
num[k] += t * num[k-2]
num[k] =  num[k] % self.mod

return num[n - 1]

def numDecodingsOfTwo(self, s):
"""
Given s of two characters, find the num of decodings if we combine the two characters
"""
if s[0] == '0':
return 0
if s in self.memorytwo:
return self.memorytwo[s]
# two '*'
if s[0] == '*' and s[1] == '*':
self.memorytwo[s] = 15
return 15 #11--19, 21--26
# one '*'
if s[0] == '*':
if s[1] <= '6':
self.memorytwo[s] = 2
return 2    # * can be 1 or 2
else:
self.memorytwo[s] = 1
return 1    # * can only be 1
if s[1] == '*':
num = 0
for i in range(1, 10):  # test * from 1 to 9
if 1 <= 10 * int(s[0]) + i <= 26:
num += 1
self.memorytwo[s] = num
return num
# no '*'
r = 1 if 1 <= int(s) <= 26 else 0
self.memorytwo[s] = r
return r
``````

Here please note that we can easily turn the space complexity into O(1) since we only depend on the previous two values of `num`. Instead of storing the whole `num` of length `n`, just store its latest two values.

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