lottery_with_dp.py

nums = [ "569815571556", "4938532894754", "1234567", "472844278465445" ]

def get_lotter_nums_rec_helper(curr_num, curr_n, rem_str):
	if curr_num > 0 and curr_num < 60:
		lottery_nums = get_lottery_nums_rec(curr_n - 1, rem_str)
		if lottery_nums:
			return [curr_num] + lottery_nums

def get_lottery_nums_rec(n, s):
	if n == 0 and s == '': return [' ']
	if n == 0 or s == '' or 2 * n < len(s): return
	lottery_nums = get_lotter_nums_rec_helper(int(s[:1]), n, s[1:])
	lottery_nums = lottery_nums or get_lotter_nums_rec_helper(int(s[:2]), n, s[2:])
	return lottery_nums

memo = {}
def get_lottery_nums_dp(n, s):
	if n == 0 and s == '': return [' ']
	if n == 0 or s == '' or 2 * n < len(s): return
	if (n, s) not in memo:
		lottery_nums = get_lotter_nums_rec_helper(int(s[:1]), n, s[1:])
		lottery_nums = lottery_nums or get_lotter_nums_rec_helper(int(s[:2]), n, s[2:])
		memo[(n, s)] = lottery_nums
	return memo[(n, s)]

def get_lottery_nums(s):
	# return get_lottery_nums_rec(7, s)
	return get_lottery_nums_dp(7, s)

for num in nums:
	lottery_nums = get_lottery_nums(num)
	if lottery_nums:
		print (num, '->', (*lottery_nums))