How to apply recursion over this problem and solve this problem

Question

The Problem is:-

Given a digit string, return all possible letter combinations of each digits according to the buttons on a telephone, that the number could represent.
The returned strings must be lexicographically sorted.

Example-1 :-
Input : “23”  
Output : ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]   

Example-2 :-
Input : “9”
Output: [“w”, “x”, “y”, “z”]

Example-3 :-
Input : “246”
Output : ["agm", "agn", "ago", "ahm", ..., "cho", "cim", "cin" "cio"] {27 elements}

I've squeezed my brain on this, and I've tried a lot but I'm not getting ahead of this part, what I've tried is to use a recursive function that zips the individual letters of each digit with each other letters and use itertools.combinations() over it, but I'm unable to complete this function and I'm unable to get ahead of this.

What I've tried is :-

times, str_res = 0, ""

def getval(lst, times):
    if times==len(lst)-1:
        for i in lst[times]:
            yield i
    else:
        for i in lst[times]:
            yield i + getval(lst, times+1)

dct = {"2":("a","b","c"), "3":("d","e","f"), "4":("g","h","i"),
     "5":("j","k","l"), "6":("m","n","o"), "7":("p","q","r","s"),
     "8":("t","u","v"), "9":("w","x","y","z"), "1":("")}

str1, res = "23", []

if len(str1)==1:
    print(dct[str1[0]])
else:
    temp = [dct[i] for i in str1]
    str_res = getval(temp, times)
    print(str_res)

Please suggest me your ideas over this problem or in completing the function...

Answer 1

It's not itertools.combinations that you need, it's itertools.product.

from itertools import product

def all_letter_comb(s, dct):
    for p in product(*map(dct.get, s)):
        yield ''.join(p)

dct = {"2":("a","b","c"), "3":("d","e","f"), "4":("g","h","i"),
     "5":("j","k","l"), "6":("m","n","o"), "7":("p","q","r","s"),
     "8":("t","u","v"), "9":("w","x","y","z"), "1":("")}

for s in ['23', '9', '246']:
    print(s)
    print(list(all_letter_comb(s, dct)))
    print()

Output:

23
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

9
['w', 'x', 'y', 'z']

246
['agm', 'agn', 'ago', 'ahm', 'ahn', 'aho', 'aim', 'ain', 'aio', 'bgm', 'bgn', 'bgo', 'bhm', 'bhn', 'bho', 'bim', 'bin', 'bio', 'cgm', 'cgn', 'cgo', 'chm', 'chn', 'cho', 'cim', 'cin', 'cio']