Dynamic programming for decoding ways


  • 0
    Z

    Straightforward dynamic programming solution.

    class Solution(object):
    	def numDecodings(self, s):
    		"""
    		:type s: str
    		:rtype: int
    		"""
    		digits = list(map(int, list(s)))[::-1] # reverse for indexing ease
    		n = len(digits)
    		if n == 0: # avoid edge case error
    			return 0
    		# for dynamic programming
    		decipher = [0]*(n+1)
    		decipher[0] = 1
    		decipher[1] = 1 if digits[0] != 0 else 0
    		for i in range(2, n+1):
    			if digits[i-1] == 0:
    				decipher[i] = 0
    			elif digits[i-1] == 1:
    				decipher[i] = decipher[i-1] + decipher[i-2]
    			elif digits[i-1] == 2:
    				if 0 <= digits[i-2] <= 6:
    					decipher[i] = decipher[i-1] + decipher[i-2]
    				else:
    					decipher[i] = decipher[i-1]
    			else:
    				decipher[i] = decipher[i-1]
    		return decipher[n]
    		# run in 52 ms
    

Log in to reply
 

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