91.md

91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

my thoughts:

1. 1 followed by 1-9 and 2 followed by 1-6 are valid. an 0 will devalid the prev num. iterate the str, count continuous valid nums,CV, res *= (1+2**(CV-1))

2. it is more complicated than 1. where the string is not necessarily valid to begin with.

my solution:

**********70 ms
class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s or s[0] == '0':
            return 0
        def validZero(s, i):
            return s[i-1] == '1' or s[i-1] == '2'
        def valid(s, i):
            return (s[i-1] == '1' or (s[i-1] == '2' and s[i] in list("123456")))
                                    
        res = 1
        i = 1
        l = len(s)
        while i < l:
            if s[i] == '0' and not validZero(s, i):
                return 0
            elif s[i] != '0' and valid(s, i):
                prev, cur = 1, 2
                j = i + 1
                while j < l and s[j] != '0' and valid(s, j):
                    t = cur
                    cur += prev
                    prev = t
                    j += 1
                if j < l and s[j] == '0':
                    if not validZero(s, j):
                        return 0
                    cur = prev
                #print(cur, i, j)
                i = j
                res *= cur
            i += 1
        return res

my comments:

from other ppl's solution:

1. logic can be simpler when start the fabonochi from 0, 0, 62ms:
class Solution:
    def connectable(a,b):
        if(a=='0'):
            return False
        elif(a=='1'):
            return b<='9' and b>='0'
        elif(a=='2'):
            return b<='6' and b>='0'
        else:
            return False
        
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s=='':
            return 0
        c,nc = (0,0)
        cur=s[0]
        if cur!='0':
            c+=1
        for i in range(1,len(s)):
            newVal = [0,0]
            if Solution.connectable(cur,s[i]):
                newVal[1]+=c
            if s[i]!='0':
                newVal[0]+=c
                newVal[0]+=nc
            c,nc = newVal
            cur = s[i]
        return c+nc
		
2. dp, 65ms:
class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        if s is None or len(s) == 0:
            return 0
        
        dp = [0 for _ in range(len(s)+1)]
        
        dp[0] = 1
        dp[1] = 0 if s[0] == '0' else 1
        for i in range(2, len(s)+1):
            t1 = int(s[i-1:i])
            t2 = int(s[i-2:i])
            if(t1>=1 and t1 <= 9):
                dp[i] += dp[i-1]
            if(t2>=10 and t2 <= 26):
                dp[i] += dp[i-2]
            
        return dp[len(s)]