Concise DP solution(Python),beats 93%


  • 0
    K

    """

    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        if not s or s[0] == '0': return 0
       
        res = [1] * len(s)
        
        for i in range(1,len(s)):
             if s[i] == '0':
                 if s[i - 1] == '1' or s[i - 1] == '2':
                    res[i] = res[i - 2]
                 else:
                    return 0
             elif s[i - 1] == '1' or s [i - 1] == '2' and s[i] < '7' :
                 res[i] = res[i - 2]  + res[i - 1]
             else:
                 res[i] = res[i - 1]
         
        return res[-1]
    

    """


Log in to reply
 

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