Total Decoding Messages

'''
eg 213
Lets think about last character 3.
Generally there are only two possibilities:

i) ith char can be attached separately to all decoded strings till i-1th character.
eg. 3 can be attached separately and make:
21,3 or 2,1,3

ii) ith char can be combined with i-1th char and attached to all decoded strings till i-2th character.
eg. 13 can be taken as one character and make:
2,13
So a dp array is required to store previous answers.
'''

#User function Template for python3
class Solution:
    def countWays(self, digits):
        dp=[0]*len(digits)
        dp[0]=1
        for i in range(1,len(digits)):
            if digits[i]!='0':
                dp[i]=dp[i-1]
            if 10<=int(digits[i-1:i+1])<=26:
                dp[i]+=dp[i-2] if i>=2 else 1
        return dp[-1]