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


'A' -> 1
'B' -> 2
...
'Z' -> 26


Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:


Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).


Example 2:


Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Starter code: class Solution:
    def numDecodings(self, s: str) -> int:
        

Solutions:
class Solution:

	def numDecodings(self, s):
		if not s:
			return 0

		def num_decode(i):
			if i == len(s):
				return 1
			if i not in memo:
				num_ways = 0
				if s[i] in single_digit_codes:
					num_ways += num_decode(i + 1)
				if s[i:i + 2] in double_digit_codes:
					num_ways += num_decode(i + 2)
				memo[i] = num_ways
			return memo[i]
		single_digit_codes = set((str(x) for x in range(1, 10)))
		double_digit_codes = set((str(x) for x in range(10, 27)))
		memo = {}
		return num_decode(0)


class Solution:

	def numDecodings(self, s):
		if not s:
			return 0
		cipher = dict(((str(k + 1), v) for (k, v) in enumerate('abcdefghijklmnopqrstuvwxyz')))
		funhash = {'': 1}

		def helpRec(s):
			if s in funhash:
				return funhash[s]
			r1 = 0
			if s[0] in cipher:
				r1 = helpRec(s[1:])
			r2 = 0
			if len(s) >= 2 and s[:2] in cipher:
				r2 = helpRec(s[2:])
			rval = r1 + r2
			funhash[s] = rval
			return rval
		return helpRec(s)


class Solution:

	def numDecodings(self, s):
		if s == None or len(s) == 0:
			return 0

		def in10(c):
			return c.isdigit() and c > '0' and (c <= '9')

		def in26(c):
			return c.isdigit() and c >= '10' and (c <= '26')
		memo = [0 for _ in range(len(s))]
		if in10(s[0]):
			memo[0] = 1
		for i in range(1, len(s)):
			if i == 1:
				if in10(s[i]):
					memo[i] = memo[i - 1]
				if in26(s[:2]):
					memo[i] = memo[i] + 1
			else:
				if in10(s[i]):
					memo[i] += memo[i - 1]
				if in26(s[i - 1:i + 1]):
					memo[i] += memo[i - 2]
		return memo[-1]


class Solution:

	def numDecodings(self, s):
		alphabet = 'abcdefghijklmnopqrstuvwxyz'
		char_code = {k: str(v) for (k, v) in zip(alphabet, list(range(1, 27)))}
		code_char = {v: k for (k, v) in list(char_code.items())}

		def numDecodingsHelper(s, hist={}):
			if not s:
				return 0
			if len(s) == 1:
				return 1 if s in code_char else 0
			if len(s) == 2:
				tmp = 1 if s in code_char else 0
				return tmp + numDecodingsHelper(s[0]) * numDecodingsHelper(s[1])
			if s[1:] not in hist:
				hist[s[1:]] = numDecodingsHelper(s[1:], hist)
			current1 = hist[s[1:]] if s[:1] in code_char else 0
			if s[2:] not in hist:
				hist[s[2:]] = numDecodingsHelper(s[2:], hist)
			current2 = hist[s[2:]] if s[:2] in code_char else 0
			return current1 + current2
		return numDecodingsHelper(s, {})