用递推法求解助记符问题

Question

给定一个非零长度的字符串电话号码，编写一个函数，以任何顺序返回此电话号码的所有助记符。

`

def phoneNumberMnemonics(phoneNumber, Mnemonics=[''], idx=0):
    number_lookup={'0':['0'], '1':['1'], '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']}

    if idx==len(phoneNumber):
        return Mnemonics
    else:
        new_Mnemonics=[]
        for letter in number_lookup[phoneNumber[idx]]:
            for mnemonic in Mnemonics:
                new_Mnemonics.append(mnemonic+letter)
        phoneNumberMnemonics(phoneNumber, new_Mnemonics, idx+1)

`

如果我使用输入"1905"，我的函数输出null。在返回语句之前使用print语句，我可以看到列表助记符是

['1w0j', '1x0j', '1y0j', '1z0j', '1w0k', '1x0k', '1y0k', '1z0k', '1w0l', '1x0l', '1y0l', '1z0l']

这是正确的答案。为什么返回null？

我不太擅长实现递归(现在？)，非常感谢您的帮助。

Answer 1

这个问题有不同的递归表达式，但最简单的思考是一个“纯函数”问题。这意味着您永远不会对递归确定的值进行变异。相反，计算新的字符串:列表等等(Python没有给您关于字符串的选择；它们总是不可变的)。以这种方式，您可以只考虑值，而不是如何存储它们和更改它们，这是非常容易出错的。

考虑这个问题的一个纯功能的方法是：

• 如果电话号码是空字符串，则返回值只是一个包含空字符串的列表.

否则，

• 将数字分解为其第一个字符和其他字符。递归地得到其余的所有助记符R。然后查找与第一个字母对应的所有字母，并将每个字母加到R的每个成员前面，以生成一个新字符串(这称为笛卡儿交叉积，经常在递归中出现)。返回所有这些字符串.

在这个表达式中，纯函数具有以下形式

M(n: str) -> list[str]:

它接受一串数字并返回一个助记符列表。

把这个想法放到python中是相当简单的：

LETTERS_BY_DIGIT = {
  '0':['0'],
  '1':['1'],
  '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'],
}

def mneumonics(n: str):
  if len(n) == 0:
    return ['']
  rest = mneumonics(n[1:])
  first = LETTERS_BY_DIGIT[n[0]]
  rtn = []  # A fresh list to return.
  for f in first:  # Cartesian cross:
    for r in rest: #   first X rest
      rtn.append(f + r);  # Fresh string
  return rtn

print(mneumonics('1905'))

请注意，这段代码根本不改变递归返回值rest。它列出了一个新的字符串列表。

当您掌握了所有Python成语之后，您将看到一种更巧妙的方式来编写同样的代码：

def mneumonics(n: str):
  return [''] if len(n) == 0 else [
    c + r for c in LETTERS_BY_DIGIT[n[0]] for r in mneumonics(n[1:])]

这是解决这个问题的最有效的代码吗？绝对不是。但无论如何，这并不是一件很实际的事情。最好是找一个简单、正确、易于理解的解决方案，而不是在你真正掌握这种思维方式之前就担心效率。

正如其他人所说，在这个问题上使用递归并不是一个很好的选择，如果这是一个生产需求。

Answer 2

为递归的最深调用生成正确的列表(助记符)。然而，它并没有被传递回以前的电话。

要解决这个问题，助记符不仅需要在“Number”块中返回，还需要将其设置为等于递归函数电话号码助记符的输出。

def phoneNumberMnemonics(phoneNumber, Mnemonics=[''], idx=0):
number_lookup={'0':['0'], '1':['1'], '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']}

print(idx, len(phoneNumber))
if idx==len(phoneNumber):
    pass
else:
    new_Mnemonics=[]
    for letter in number_lookup[phoneNumber[idx]]:
        for mnemonic in Mnemonics:
            new_Mnemonics.append(mnemonic+letter)
    Mnemonics=phoneNumberMnemonics(phoneNumber, new_Mnemonics, idx+1)
return Mnemonics

我仍然觉得我对递归的理解不够成熟。欢迎咨询、反馈和澄清。