Key is to realize that at each position (i) you can generate combinations based on the integer value of the substring of s[i-1:i+1]. If this value is 0 (00) or is greater than 26 but the mod base 10 of it is 0, then we can't encode that value. If this value is <= 26 then we can add # of combinations generated by both the digit before and 2 digits before. If the value is > 26 then we can't generate additional combinations.
def numDecodings(self, s): """ :type s: str :rtype: int """ if len(s) < 1 or s == "0": return 0 prev = cnt = 1 for i in range(1, len(s)): b, t = int(s[i-1]), int(s[i]) curr = b * 10 + t if curr == 0: return 0 if t == 0: if curr > 26: return 0 cnt, prev = prev, cnt elif b == 0 or curr > 26: prev = cnt else: prev, cnt = cnt, prev + cnt return cnt