给定映射：
A: 1
B: 2
C: 3
...
...
...
Z: 26
找到可以表示数字的所有可能方式。例如。对于输入：“121”，我们可以将其表示为：
ABA [using: 1 2 1]
LA [using: 12 1]
AU [using: 1 21]
我试着考虑使用某种动态编程方法，但我不知道如何继续。我在技术面试中被问到这个问题。
这是我能想到的解决方案，如果这看起来不错，请告诉我：
A[i]: Total number of ways to represent the sub-array number[0..i-1] using the integer to alphabet mapping.
解决方案[我错过了什么吗？]：
A[0] = 1 // there is only 1 way to represent the subarray consisting of only 1 number
for(i = 1:A.size):
A[i] = A[i-1]
if(input[i-1]*10 + input[i] < 26):
A[i] += 1
end
end
print A[A.size-1]
为了获得计数，动态编程方法非常简单：
A[0] = 1
for i = 1:n
A[i] = 0
if input[i-1] > 0 // avoid 0
A[i] += A[i-1];
if i > 1 && // avoid index-out-of-bounds on i = 1
10 <= (10*input[i-2] + input[i-1]) <= 26 // check that number is 10-26
A[i] += A[i-2];
如果您想要列出所有表示，动态编程并不是特别适合这种情况，您最好使用简单的递归算法。
经过研究，我偶然发现了这个视频https://www.youtube.com/watch?v=qli-JCrSwuk。
首先，我们需要找到一种直观的方法来列举所有可能性。我的简单结构如下。
let us assume a simple way to represent your integer in string format.
a1 a2 a3 a4 ....an, for instance in 121 a1 -> 1 a2 -> 2, a3 -> 1
现在，
我们需要找出在两个字符之间放置+符号的可能性。 +表示字符串联。
a1 - a2 - a3 - .... - an, - shows the places where '+' can be placed. So, number of positions is n - 1, where n is the string length.
假设一个位置可能有也可能没有+符号应表示为一个位。因此，这归结为n-1的长度可以有多少不同的位串，这显然是2 ^（n-1）。现在为了列举可能性，遍历每个位串并在相应位置放置右+符号以获得每个表示，
以你的例子，121
Four bit strings are possible 00 01 10 11
1 2 1
1 2 + 1
1 + 2 1
1 + 2 + 1
And if you see a character followed by a +, just add the next char with the current one and do it sequentially to get the representation,
x + y z a + b + c d
would be (x+y) z (a+b+c) d
希望能帮助到你。
当然，你必须处理大于等于26的整数的边缘情况。
我认为，通过所有可能的组合进行递归遍历会很好：
mapping = {"1":"A", "2":"B", "3":"C", "4":"D", "5":"E", "6":"F", "7":"G",
"8":"H", "9":"I", "10":"J",
"11":"K", "12":"L", "13":"M", "14":"N", "15":"O", "16":"P",
"17":"Q", "18":"R", "19":"S", "20":"T", "21":"U", "22":"V", "23":"W",
"24":"A", "25":"Y", "26":"Z"}
def represent(A, B):
if A == B == '':
return [""]
ret = []
if A in mapping:
ret += [mapping[A] + r for r in represent(B, '')]
if len(A) > 1:
ret += represent(A[:-1], A[-1]+B)
return ret
print represent("121", "")
假设您只需要计算组合数。
假设0后跟[1,9]中的整数不是有效的连接，那么蛮力策略将是：
Count(s,n)
x=0
if (s[n-1] is valid)
x=Count(s,n-1)
y=0
if (s[n-2] concat s[n-1] is valid)
y=Count(s,n-2)
return x+y
更好的策略是使用分而治之：
Count(s,start,n)
if (len is even)
{
//split s into equal left and right part, total count is left count multiply right count
x=Count(s,start,n/2) + Count(s,start+n/2,n/2);
y=0;
if (s[start+len/2-1] concat s[start+len/2] is valid)
{
//if middle two charaters concatenation is valid
//count left of the middle two characters
//count right of the middle two characters
//multiply the two counts and add to existing count
y=Count(s,start,len/2-1)*Count(s,start+len/2+1,len/2-1);
}
return x+y;
}
else
{
//there are three cases here:
//case 1: if middle character is valid,
//then count everything to the left of the middle character,
//count everything to the right of the middle character,
//multiply the two, assign to x
x=...
//case 2: if middle character concatenates the one to the left is valid,
//then count everything to the left of these two characters
//count everything to the right of these two characters
//multiply the two, assign to y
y=...
//case 3: if middle character concatenates the one to the right is valid,
//then count everything to the left of these two characters
//count everything to the right of these two characters
//multiply the two, assign to z
z=...
return x+y+z;
}
蛮力解决方案具有T(n)=T(n-1)+T(n-2)+O(1)的时间复杂度，这是指数级的。
分而治之的解决方案具有T(n)=3T(n/2)+O(1)的时间复杂度，即O（n ** lg3）。
希望这是正确的。
像这样的东西？
Haskell代码：
import qualified Data.Map as M
import Data.Maybe (fromJust)
combs str = f str [] where
charMap = M.fromList $ zip (map show [1..]) ['A'..'Z']
f [] result = [reverse result]
f (x:xs) result
| null xs =
case M.lookup [x] charMap of
Nothing -> ["The character " ++ [x] ++ " is not in the map."]
Just a -> [reverse $ a:result]
| otherwise =
case M.lookup [x,head xs] charMap of
Just a -> f (tail xs) (a:result)
++ (f xs ((fromJust $ M.lookup [x] charMap):result))
Nothing -> case M.lookup [x] charMap of
Nothing -> ["The character " ++ [x]
++ " is not in the map."]
Just a -> f xs (a:result)
输出：
*Main> combs "121"
["LA","AU","ABA"]
只是我们广度优先搜索。
例如121
从第一个整数开始，首先考虑1个整数字符，将1映射为a，然后将21个整数字符映射12留给L，留下1。
以下是基于我在此讨论的解决方案：
private static int decoder2(int[] input) {
int[] A = new int[input.length + 1];
A[0] = 1;
for(int i=1; i<input.length+1; i++) {
A[i] = 0;
if(input[i-1] > 0) {
A[i] += A[i-1];
}
if (i > 1 && (10*input[i-2] + input[i-1]) <= 26) {
A[i] += A[i-2];
}
System.out.println(A[i]);
}
return A[input.length];
}
使用标准DP算法可以在o（fib（n + 2））时间内完成此问题。我们有n个子问题和按钮我们可以用o（fib（i））时间解决尺寸i的每个问题。对该系列求和得到fib（n + 2）。
如果你仔细考虑这个问题，你会发现它是斐波那契系列。我采用了标准的Fibonacci代码，并根据我们的条件进行了更改。
这个空间显然与所有解决方案的大小有关（fib（n））。
考虑这个伪代码：
Map<Integer, String> mapping = new HashMap<Integer, String>();
List<String > iterative_fib_sequence(string input) {
int length = input.length;
if (length <= 1)
{
if (length==0)
{
return "";
}
else//input is a-j
{
return mapping.get(input);
}
}
List<String> b = new List<String>();
List<String> a = new List<String>(mapping.get(input.substring(0,0));
List<String> c = new List<String>();
for (int i = 1; i < length; ++i)
{
int dig2Prefix = input.substring(i-1, i); //Get a letter with 2 digit (k-z)
if (mapping.contains(dig2Prefix))
{
String word2Prefix = mapping.get(dig2Prefix);
foreach (String s in b)
{
c.Add(s.append(word2Prefix));
}
}
int dig1Prefix = input.substring(i, i); //Get a letter with 1 digit (a-j)
String word1Prefix = mapping.get(dig1Prefix);
foreach (String s in a)
{
c.Add(s.append(word1Prefix));
}
b = a;
a = c;
c = new List<String>();
}
return a;
}
旧的问题，但添加一个答案，以便人们可以找到帮助
我花了一些时间来理解这个问题的解决方案 - 我引用了接受的答案和@Karthikeyan的答案以及geeksforgeeks的解决方案并编写了我自己的代码如下：
要了解我的代码，首先要了解以下示例：
decodings([1, 2])是"AB"或"L"所以decoding_counts([1, 2]) == 2decodings([1, 2, 1])是"ABA"，"AU"，"LA"等decoding_counts([1, 2, 1]) == 3使用上面两个例子让我们评估decodings([1, 2, 1, 4])：
4作为单个数字解码为字母'D'，我们得到decodings([1, 2, 1, 4]) == decoding_counts([1, 2, 1])因为[1, 2, 1, 4]将被解码为"ABAD"，"AUD"，"LAD"4与之前的1组合为14作为单个解码为字母N，我们得到decodings([1, 2, 1, 4]) == decoding_counts([1, 2])因为[1, 2, 1, 4]将被解码为"ABN"或"LN"下面是我的Python代码，阅读评论
def decoding_counts(digits):
# defininig count as, counts[i] -> decoding_counts(digits[: i+1])
counts = [0] * len(digits)
counts[0] = 1
for i in xrange(1, len(digits)):
# case:- "taking next digit as single digit"
if digits[i] != 0: # `0` do not have mapping to any letter
counts[i] = counts[i -1]
# case:- "combining next digit with the previous digit"
combine = 10 * digits[i - 1] + digits[i]
if 10 <= combine <= 26: # two digits mappings
counts[i] += (1 if i < 2 else counts[i-2])
return counts[-1]
for digits in "13", "121", "1214", "1234121":
print digits, "-->", decoding_counts(map(int, digits))
输出：
13 --> 2
121 --> 3
1214 --> 5
1234121 --> 9
注意：我认为输入digits不是从0开始，只包含0-9并且具有足够的长度