Given a string, find the count of possible codes that string can generate using Python

Question

If a=1, b=2, c=3,....z=26. I want to find the count of possible codes that string can generate using Python

For example:

get_combination('12')
Output: 2
// The possible decodings are "AB", "L"

get_combination('121')
Output: 3
// The possible decodings are "ABA", "AU", "LA"

get_combination('1234')
Output: 3
// The possible decodings are "ABCD", "LCD", "AWD"

Here is the code for that. but the time complexity is more. Can someone have simpler solution than this

def get_combination(string):
    def get_branchs(string):
        if not string or len(string) == 1:
            return 0
        if string[0:2] <= '26':
            if '0' not in string[1:3]:
                return 1 + get_branchs(string[1:]) + get_branchs(string[2:])
            else:
                return get_branchs(string[2:])
        else:
            return get_branchs(string[1:])
    return 1 + get_branchs(string)

Answer 1

This is the simplest form I've got:

def get_num_codes(number):
    if not number:
        return 1
    # If you want to allow for "stray zeros" at the end remove this if block
    if number == "0":
        return 0
    count = get_num_codes(number[1:])
    if number[0] != "0" and len(number) > 1 and number[:2] <= "26":
        count += get_num_codes(number[2:])
    return count

Performance of both versions is comparable:

%timeit get_combination("123412432414324231123412")
>>> 1000 loops, best of 3: 1.83 ms per loop
%timeit get_num_codes("123412432414324231123412")
>>> 1000 loops, best of 3: 1.87 ms per loop

Answer 2

As Trincot commented, you could save time on the string slicing by passing an offset to your get_branch function, so you don't have to pass string or a string slice.

So here's my modified version, only using an offset as a parameter for the internal get_branch function:

def get_combination(string):
    def get_branchs(offset=0):
        if len(string)-offset <= 1:
            return 0
        if string[offset:2+offset] <= '26':
            if '0' not in string[1+offset:3+offset]:
                return 1 + get_branchs(1+offset) + get_branchs(2+offset)
            else:
                return get_branchs(2+offset)
        else:
            return get_branchs(1+offset)
    return 1 + get_branchs()

There are some remaining slicing to compare to 26 and to check if 0 is in the sub-string. Testing against indexes would be an alternative, but I'm unsure of how this would behave when indexes are out of bounds (slicing doesn't mind, index access does)

Note: I hope to be on-topic when answering, maybe codereview would be best for this kind of question & answer.