如何对这个问题应用递归并解决这个问题

Question

问题是：-

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}

我在这上面绞尽脑汁，我已经尝试了很多，但我并没有超越这一部分，我尝试的是使用一个递归函数来压缩每个字母的单个字母数字与其他字母并在其上使用 itertools.combinations()，但我无法完成此功能并且我无法领先于此。

我试过的是：-

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)

请就此问题或完成功能提出您的想法...

Answer 1

您需要的不是 itertools.combinations，而是 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()

输出：

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']

Answer 2

如果我没记错的话这是leet代码问题。您可以在那里找到多个答案。

如何对这个问题应用递归并解决这个问题

How to apply recursion over this problem and solve this problem

python-3.x

loops

dictionary

recursion

generator