Decode Ways

Question

What is the most efficient algorithm to determine the total number of ways to decode a given string of digits?

Example 1

Input: "12" 
Output: 2 (Possible ways to decode: "AB" or "L")

Solution

▭

all//Decode Ways.py

def decodeWays(s):
    if s == "" or s[0] == '0':
        return 0

    dp = [0] * (len(s)+1)

    dp[0] = 1
    dp[1] = 1

    for i in range(2, len(s)+1):
        if (s[i-1] > '0'):
            dp[i] = dp[i-1]

        if (s[i-2] == '1' or (s[i-2] == '2' and s[i-1] < '7') ):
            dp[i] += dp[i-2]

    return dp[len(s)]

▯

all//Decode Ways.py

def decodeWays(s):
    if s == "" or s[0] == '0':
        return 0

    dp = [0] * (len(s)+1)

    dp[0] = 1
    dp[1] = 1

    for i in range(2, len(s)+1):
        if (s[i-1] > '0'):
            dp[i] = dp[i-1]

        if (s[i-2] == '1' or (s[i-2] == '2' and s[i-1] < '7') ):
            dp[i] += dp[i-2]

    return dp[len(s)]