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

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.
"""


def count_ways_naive(s, start=0, cache=None):
    if cache is None:
        cache = {}

    if start + 1 >= len(s):
        return 1

    if start in cache:
        return cache[start]

    count = 0
    if s[start] == '1':
        count += count_ways_naive(s, start + 1, cache) + count_ways_naive(s, start + 2, cache)
    elif s[start] == '2':
        count += count_ways_naive(s, start + 1, cache)
        if s[start + 1] <= '6':
            count += count_ways_naive(s, start + 2, cache)
    else:
        count += count_ways_naive(s, start + 1, cache)

    cache[start] = count
    return count


def count_ways(s):
    if len(s) == 0:
        return 0

    prev2 = 1
    prev1 = 1
    for i in xrange(1, len(s)):
        if s[i] == '0':
            if s[i - 1] not in {'1', '2'}:
                return 0
            prev2, prev1 = prev2, prev2
        elif '09' < s[i - 1:i + 1] <= '26':
            prev2, prev1 = prev1, prev1 + prev2
        else:
            prev2, prev1 = prev1, prev1
    return prev1


if __name__ == '__main__':
    print count_ways('12')
    print count_ways('1234')
    print count_ways('3914211')
