我刚刚遇到了一个有趣的面试风格类型的问题，我无法理解。
基本上，给定一个数字到字母映射[1:A, 2:B, 3:C ...]，打印出所有可能的组合。
例如“123”将生成[ABC, LC, AW]，因为它可以分为 12,3 和 1,23。
我认为它必须是某种类型的递归函数，它检查大小为 1 和 2 的窗口，如果它是有效的字母映射，则附加到先前的结果。
如果有人可以制定一些伪/python代码，将不胜感激。
问问题
1566 次
6 回答
1
像一棵树一样简单
假设你给了“1261”
用它构造一棵树 Root 。
通过定义节点（左，右），其中左总是直接映射，右是组合
版本假设如果你把给定的数字作为 1261
1261 ->
(1(261) ,12(61)) -> 1 是左节点（直接映射 -> a）12 是右节点（combo-map1,2->L）
(A(261) , L(61)) ->
(A(2(61),26(1))) ,L(6(1)) ->
(A(B(6(1)),Z(1)),L(F(1))) ->
(A(B(F(1)),Z(A)),L(F(A))) ->
(A(B(F(A)),Z(A)),L(F(A)))
所以现在你已经得到了所有的叶子节点..
只需打印从根到叶节点的所有路径，这将为您提供所有可能的组合。
就像在这种情况下
ABFA , 氮杂 , LFA
因此，一旦您完成树的构建，只需打印从根到节点的所有路径
这是你的要求。
于 2013-04-24T07:36:40.467 回答
1
所以我设法拼凑出一个答案，它不像我想要的那样像pythonic，可能会有一些冗余，但它可以与 123 示例一起输出 ABC、AW 和 LC。
我明天可能会清理它（或者如果有人想清理它），只是发布它以防有人也在处理它并且想知道。
def num_to_alphabet(numbers, ans = ""):
if not numbers:
print ans
numbers = str(numbers)
window = numbers[:2]
alph = string.uppercase
ans = ans[:]
ans2 = ans[:]
window_val = ""
try:
if window[0]:
val = int(numbers[0])-1
if alph[val]:
ans += alph[val]
num_to_alphabet(numbers[1:], ans)
if window[1]:
val = int(window) -1
if alph[val]:
ans2 += alph[val]
if len(window) > 1:
num_to_alphabet(numbers[2:],ans2)
else:
num_to_alphabet(numbers[1:],ans2)
except IndexError:
pass
于 2013-04-24T07:37:15.670 回答
0
我仍然不确定描述，但是这个 Python 脚本首先将 num 划分为它的“breaks”，然后尝试将每个 break 成员作为一个整体作为其对应字符的索引；然后将成员的每个数字转换为单词的字母。在显示数字“123”的所有字母/单词转换的总和之前显示了这两个贡献
>>> import string
>>> mapping ={str(n):ch for n,ch in zip(range(1,27), string.ascii_uppercase)}
>>> num = '123'
>>> [[num[:i], num[i:]] for i in range(len(num)+1)]
[['', '123'], ['1', '23'], ['12', '3'], ['123', '']]
>>> breaks = set(part for part in sum(([num[:i], num[i:]] for i in range(len(num)+1)), []) if part)
>>> breaks
{'123', '12', '3', '1', '23'}
>>> as_a_whole = [mapping[p] for p in breaks if p in mapping]
>>> as_a_whole
['L', 'C', 'A', 'W']
>>> by_char = [''.join(mapping[n] for n in p) for p in breaks]
>>> by_char
['ABC', 'AB', 'C', 'A', 'BC']
>>> everything = sorted(set(as_a_whole + by_char))
>>> everything
['A', 'AB', 'ABC', 'BC', 'C', 'L', 'W']
>>>
于 2013-04-24T17:01:24.217 回答
0
所以，我也想解决这个问题，因为这实际上是一个很酷的问题。所以这是我的解决方案：
如果我们暂时忽略对字符串的翻译，我们本质上是在寻找一个集合的分区。所以对于输入123，我们有一个集合{1, 2, 3}并且正在寻找分区。但是在这些分区中，只有那些保持输入原始顺序的分区才是有趣的。所以我们实际上并不是在谈论最后的集合（顺序无关紧要）。
不管怎样，我把这个叫做“有序分区”——我不知道它是否真的存在一个术语。我们可以使用递归轻松生成这些有序分区：
def orderedPartitions(s):
if len(s) == 0:
yield []
return
for i in range(1, len(s)+1):
for p in orderedPartitions(s[i:]):
yield [s[:i]] + p
对于字符串 input '123'，这为我们提供了以下部分，这正是我们正在寻找的：
['1', '2', '3']
['1', '23']
['12', '3']
['123']
现在，回到要求翻译成字符串的原始问题，我们需要做的就是检查每个分区，如果它们只包含有效数字，即 1 到 26。如果是这样，翻译那些数字并返回结果字符串。
import string
def alphaCombinations(s):
for partition in orderedPartitions(str(s)):
# get the numbers
p = list(map(int, partition))
# skip invalid numbers
if list(filter(lambda x: x < 1 or x > 26, p)):
continue
# yield translated string
yield ''.join(map(lambda i: string.ascii_uppercase[i - 1], p))
它有效：
>>> list(alphaCombinations(123))
['ABC', 'AW', 'LC']
>>> list(alphaCombinations(1234))
['ABCD', 'AWD', 'LCD']
>>> list(alphaCombinations(4567))
['DEFG']
于 2013-04-24T15:48:22.763 回答
0
以下答案递归地尝试当前位置的所有可能性（有两个以上！）并继续字符串的其余部分。而已。
from string import ascii_uppercase
def alpha_combinations(s):
if len(s) == 0:
yield ""
return
for size in range(1, len(s) + 1):
v = int(s[:size])
if v > 26:
break
if v > 0:
c = ascii_uppercase[v - 1]
for ac in alpha_combinations(s[size:]):
yield c + ac
print(list(alpha_combinations(input())))
它需要一个数字作为字符串。它为101010( ['AAJ', 'AJJ', 'JAJ', 'JJJ']) 提供正确的输出。（我认为其他一些解决方案不能正确处理零。）
于 2013-04-24T12:27:06.413 回答
0
charMap = {'1':'A', '2':'B' ... }
def getNodes(str):
results = []
if len(str) == 0: return results
c = str[0]
results.append(c)
results = results.join(c.join(getNodes(str[1:])))
if str[:2] in charMap.keys(): results = results.join(c.join(getNodes(str[2:])))
return results
def mapout(nodes):
cArray = []
for x in nodes:
cx = ''
for y in x:
cx = cx + charMap.get(y)
cArray.append(cx)
return cArray
res = getNodes('12345')
print(mapout(res))
未经测试，但我相信这符合您正在寻找的内容。
于 2013-04-24T05:40:29.387 回答