电话号码代表的数字排列

Question

我在2天内接受采访,我很难找到这个问题的解决方案:我想要做的是......对于任何电话号码......程序应该打印出它代表的所有可能的字符串.例如.)数字中的2可以用'a'或'b'或'c'代替,3代表'd''e''f'等.这样可以形成多少可能的排列给出了电话号码.我不希望任何人为它编写代码......一个好的算法或伪代码会很棒.

谢谢

Answer 1

这是流行的对应表:

d = { '2': "ABC",
'3': "DEF",
'4': "GHI",
'5': "JKL",
'6': "MNO",
'7': "PQRS",
'8': "TUV",
'9': "WXYZ",
}

鉴于此或任何其他d(可执行的)伪代码将一串数字转换为所有可能的字母串:

def digstolets(digs):
  if len(digs) == 0:
    yield ''
    return
  first, rest = digs[0], digs[1:]
  if first not in d:
    for x in digstolets(rest): yield first + x
    return
  else:
    for x in d[first]:
      for y in digstolets(rest): yield x + y

可调整取决于你想对输入字符串中不包含2和9包含的字符做什么(这个版本只是回应它们! - ).

例如,

print list(digstolets('1234'))

在这个版本中发出

['1ADG', '1ADH', '1ADI', '1AEG', '1AEH', '1AEI', '1AFG', '1AFH', '1AFI', 
 '1BDG', '1BDH', '1BDI', '1BEG', '1BEH', '1BEI', '1BFG', '1BFH', '1BFI',
 '1CDG', '1CDH', '1CDI', '1CEG', '1CEH', '1CEI', '1CFG', '1CFH', '1CFI']

编辑:OP要求更多解释,这是一次尝试.函数digstolets(数字到字母)采用一串数字digs并产生一系列字符串,可以是字母或"非数字". 0并且在此1计算为非数字,因为它们不会扩展为字母,就像空格和标点符号一样 - 只包括2要9包含的数字扩展为字母(大多数情况下各有三种可能,两种情况下有四种,因为7可以扩展到任何PQRS和9可以扩展到任何WXYZ).

首先,基本情况:如果没有剩下(字符串digs为空),唯一可能的结果是空字符串,就是这样,这个递归调用完成,完成,kaput.

如果digs非空,则可以将其拆分为"头部",第一个字符和"尾部",其余部分(第一个字符后面的0个或多个字符).

如果是非数字,"head"要么保持在输出中,要么保持不变; 如果是数字,则扩展为三种或四种可能性中的任何一种.在任何一种情况下,头部的一个,三个或四个可能的扩展必须与尾部的每个可能的扩展连接,即递归调用,以获得尾部的所有可能的扩展(因此我们遍历所有可能的扩展)尾部的扩展,并且产生头部的一个,三个或四个可能的扩展中的每一个与每个可能的尾部扩展连接在一起.然后,再一次,这就是全部,伙计们.

我不知道如何用更基本的术语来表达这一点 - 如果在此之后OP仍然丢失,我只能建议对递归的所有内容进行认真的全面审查.删除递归以支持显式维护的堆栈不能简化这个概念性展示 - 取决于所涉及的语言(听听OP完全适合的语言会很好!),递归消除可能是一个重要的优化,但是它从来不是概念上的简化 ......! - )