def get_seq_in_tree(tree, choice):
    if type(tree) != dict:
        if choice == tree:
            return [choice]
return []
for i in range(1, len(choice) + 1):
    if choice[:i] in tree:
        return [choice[:i]] + get_seq_in_tree(tree[choice[:i]], choice[i:])
return []

def seq_can_end_here(tree, seq):
    res = []
last = tree
for e, c in enumerate(seq):
    if '' in last[c]:
        res.append(e + 1)
last = last[c]
return res

def build_tree(choices):
    tree = {}
choices = sorted(choices)
for choice in choices:
    last = tree
for c in choice:
    if c not in last:
        last[c] = {}
last = last[c]
last[''] = None
return tree
solution_cache = {}
ncalls = 0

def solve(tree, number):
    global solution_cache
global ncalls
ncalls += 1
if number in solution_cache:
    return solution_cache[number]
solutions = []
seq = get_seq_in_tree(tree, number)
endings = seq_can_end_here(tree, seq)
for i in reversed(endings):
    current_solution = []
current_solution.append(number[:i])
if i == len(number):
    solutions.append(current_solution)
else:
    next_solution = solve(tree, number[i:])
if next_solution:
    solutions.append(current_solution + next_solution)
if not solutions:
    return None
shortest_solution = sorted([(len(solution), solution) for solution in
    solutions])[0][1]
solution_cache[number] = shortest_solution
return shortest_solution

def get_it_done(choices, number):
    tree = build_tree(choices)
solution = solve(tree, number)
return solution
if __name__ == '__main__':
    examples = [(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '10',
        '20', '30', '40', '50', '60', '70', '80', '90', '100', '200', '300',
        '400', '500', '600', '700', '800', '900',
        '012345678910203040506070'],
        '0123456789102030405060708090100200300400500600700800900'), (['0',
        '1', '10', '100'], '100'), (['10', '20', '30', '40', '50', '60',
        '70', '80', '90', '012345678910203040506070',
        '101234567891020304050', '6070809010020030040050', '0600700800900'],
        '10123456789102030405060708090100200300400500600700800900'), (['12',
        '34', '56', '78', '90', '890'], '1234567890'), (['1', '2', '3',
        '12', '23', '34'], '1234'), (['0', '1', '10', '100'], '10010')]
score = 0
for choices, large_number in examples:
    res = get_it_done(choices, large_number)
flag = ''.join(res) == large_number
print("""{0}
{1}
{2} --> {3}""".format(large_number, ''.join(res), res, flag))
print('-' * 80)
score += flag
print('Score: {0}/{1} = {2:.2f}%'.format(score, len(examples), score / len(
    examples) * 100))
How to split text into chunks minimizing the solution?