decode_ways.py

"""
# Decode Ways
A string made up of digits can be decoded into uppercase English
letters using the following mapping:
'A'-> "1", 'B' -> "2", 'Z' -> "26"
To decode a given numeric string, you must partition the digits
into valid groups, where each group represents a number that maps
to a letter.
For example, the string "2715" can be decoded as:
* "BGAE" with the grouping (2 7 1 5)
* "BGO" with the grouping (2 7 15)
Given a string s containing only digits, return the number of
different ways to decode it. You may assume that the answer fits in
a 32-bit integer.

----------------------------------

112012
1|1|20|1|2
1|1|20|12
11|20|1|2
11|20|12


Actions = {1 digit, 2 digits}
States = {i}
Value = number of ways

"""

alphabet = { str(i+1) : chr(ord('a') + i).upper() for i in range(26)}

def decode_ways(code):
    n = len(code)
    V = [0] * n
    V[0] = 1 if code[0] in alphabet else 0

    for i in range(1, n):
        if code[i] in alphabet: # single digit
            V[i] += V[i-1]

        if code[i-1:i+1] in alphabet:  # double digit
            V[i] += V[i-2] if i >= 2 else 1

    return V[n-1]



if __name__ == '__main__':
    from utils import test
    test(decode_ways('1212211122'), 89)
    test(decode_ways('1201'), 1)  # Only "ABA" is valid
    test(decode_ways('1111'), 5)  # "AAAA", "KAA", "AKA", "AAK", "KK"
    test(decode_ways('112012'), 4)
    test(decode_ways('0'), 0)
    test(decode_ways('2715'), 2)  # "BGAE", BGO"
    test(decode_ways('23'), 2)  # "BC" (2 3) or "W" (23).
    test(decode_ways('30'), 0)
    test(decode_ways('12'), 2)  # "AB" (1 2) or "L" (12)
    test(decode_ways('226'), 3)  # "BZ" (2 26) or "VF" (22 6) or "BBF" (2 2 6)
    test(decode_ways('06'), 0)  # Leading zero is invalid
    test(decode_ways('27'), 1)  # Only "BG" is valid as 27 > 26
    test(decode_ways('111'), 3)  # "AAA" (1 1 1) or "KA" (11 1) or "AK" (1 11)
    test(decode_ways('1234'), 3)  # "ABCD" (1 2 3 4) or "LCD" (12 3 4) or "AWD" (1 23 4)
    test(decode_ways('12121'), 8)  # "ABABA", "ABAU", "AUBA", "LAA", "ALA", "ALU", "LBA", "LU"
    test(decode_ways('1111'), 5)  # "AAAA", "KAA", "AKA", "AAK", "KK"
    test(decode_ways('2611055'), 2)  # "B F A J E E", "Z A J E E"

    from utils import plot_time_complexity
    plot_time_complexity(decode_ways, lambda n: '1'*n)