num_char_encodings.py

# The English alphabet has 26 characters.
# Each character is encoded according to their position in the alphabet.
# E.g. A = 1, B = 2, C = 3 and so on.
# Given a sequence of digits, determine how many valid character sequences can be made from it.
# E.g. 123 = 3: ABC (1, 2, 3) or LC (12, 3) or AW (1, 23)
# Another example, 271 only has 1: BGA (2, 7, 1) as 27 and 71 are not valid character encodings.

def num_char_encodings(digits):
    dp = [1, 1]
    for n, digit in enumerate(digits[1:], 1):

        with_previous = int(str(digits[n-1]) + str(digit))
        if with_previous <= 26:
            dp.append(dp[n] + dp[n-1])
            continue
        dp.append(dp[n])

    print dp[-1]
    return dp[-1]

num_char_encodings([1])  # 1
num_char_encodings([1, 6])  # 2: [1, 6] [16]
num_char_encodings([1, 6, 2])  # 2: [1, 6, 2] [16, 2]
num_char_encodings([1, 6, 2, 4])  # 4 [1, 6, 2, 4] [16, 2, 4] [1, 6, 24] [16, 24]
num_char_encodings([1, 6, 2, 4, 1])  # 4 [1, 6, 2, 4, 1] [16, 2, 4, 1] [1, 6, 24, 1] [16, 24, 1]

# Total: 8
# take the single 5 only and append to orderings of [1, 6, 2, 4, 1]
# [1, 6, 2, 4, 1, 5] [16, 2, 4, 1, 5] [1, 6, 24, 1, 5] [16, 24, 1, 5]
# take the previous number, if <= 26 then we can append to orderings of [1, 6, 2, 4]
# [1, 6, 2, 4, 15] [16, 2, 4, 15] [1, 6, 24, 15] [16, 24, 15]
num_char_encodings([1, 6, 2, 4, 1, 5])