您会收到一条仅包含数字的编码消息。还为您提供以下映射
A : 1
B : 2
C : 3
..
Z : 26
给定一条编码的消息，计算它可以被解码的方式的数量。
eg：12可以用2种方式解码：（A，B）和（L）
我想出了接受数字作为字符串字符然后检查每个数字的算法：
1.If the first digit of the string array is zero , return zero.
2.for each of its digit(i) from 1 to n perform:
if str[i-1]>2 || (str[i-1]=='2' && str[i]>'6')
return 0;
if(str[i]==0)
return 0;
每次我尝试将消息中的第一个数字编码为一个字母，或者如果可能的话，我可以将前两个数字编码为一个字母。当遇到单个 '0' 或遇到 '32' 等无法编码时，只需返回即可。
这个问题可以更有效地解决吗？
您当前对该问题的近似值是正确的。虽然，您需要非常小心地处理所有不清楚的情况，这将使我的回答比需要的时间长一点。
看待这个问题的正确方法是从动态规划的角度。让我们将您的输入字符串视为message，并将其长度视为n。
要解码一个message字符n，您需要知道可以使用多少种方式解码message使用n - 1字符和message使用n - 2字符。那是，
n字符的消息。
1
1 2 3 4 5 6 7 8 9 0 1
+---+---+---+---+---+---+---+---+---+---+---+
message | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 4 | 1 | 2 |
+---+---+---+---+---+---+---+---+---+---+---+
使用 1 个数字和一个message字符n - 1长。
1
1 2 3 4 5 6 7 8 9 0 1
+---+---+---+---+---+---+---+---+---+---+ +---+
message | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 4 | 1 | + | 2 |
+---+---+---+---+---+---+---+---+---+---+ +---+
使用 2 位数字和一个message字符n - 2长。
1
1 2 3 4 5 6 7 8 9 0 1
+---+---+---+---+---+---+---+---+---+ +---+---+
message | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 4 | + | 1 | 2 |
+---+---+---+---+---+---+---+---+---+ +---+---+
现在，你可能会问自己：
我如何计算可以解码字符和字符
message的方式有多少？n - 1n - 2
实际上是一样的。最终，您会将其简化为基本情况。
假设ways[n]它可以解码字符message的方式数量。n然后，你可以ways[n]这样放，
ways[n] = ways[n - 1] + ways[n - 2]
（由于不知道如何定义空字符串的方式数，我将其视为1。）
在适当的约束和基本情况下，
n = 0,
ways[n] = 1
n > 1并且message[n]是有效的并且message[n - 1:n]是有效的，
ways[n] = ways[n - 1] + ways[n - 2]
n > 1并且message[n]有效message[n - 1:n]和无效，
ways[n] = ways[n - 1]
n > 1并且message[n]是无效的并且message[n - 1:n]是有效的，
ways[n] = ways[n - 2]
否则，
ways[n] = 0
C 中的迭代decode函数可能如下所示，
int decode(char* message, size_t len) {
int i, w, ways[] = { 1, 0 };
for(i = 0, w; i < len; ++i) {
w = 0;
if((i > 0) && ((message[i - 1] == '1') || (message[i - 1] == '2' && message[i] < '7'))) {
w += ways[1];
}
if(message[i] > '0') {
w += ways[0];
}
ways[1] = ways[0];
ways[0] = w;
}
return ways[0];
}
你可以在ideone看到它。我正在使用恒定的额外内存进行计算。
我想我会用我评论的 python 代码来补充@Alexander 的帖子，因为我花了一些时间来弄清楚动态编程解决方案是如何工作的。我发现意识到这与编写斐波那契函数有多么相似是很有用的。我还在我的 github 上上传了完整的代码、测试和运行时比较以及天真的递归。
def number_of_decodings_fast(code):
""" Dynamic programming implementation which runs in
O(n) time and O(1) space.
The implementation is very similar to the dynamic programming
solution for the Fibonacci series. """
length = len(code)
if (length <= 1):
# assume all such codes are unambiguously decodable
return 1
else:
n_prev = 1 # len 0
n_current = 1 # len 1
for i in range(1,length):
if (
# a '1' is ambiguous if followed by
# a digit X=[1-9] since it could be
# decoded as '1X' or '1'+'X'
code[i-1]=='1' and
code[1] in [str(k) for k in (range(1,10))]
) or (
# a '2' is ambiguous if followed by
# a digit X=[1-6] since it could be
# decoded as '2X' or '2'+'X'
code[i-1]=='2' and
code[i] in [str(k) for k in range(1,7)]
):
# New number of decodings is the sum of
# decodings obtainable from the code two digits back
# (code[0:(i-2)] + '[1-2]X' interpretation)
# and decodings obtainable from the code one digit back
# (code[0:(i-1)] + 'X' interpretation).
n_new = n_prev + n_current
else:
# New number of decodings is the same as
# that obtainable from the code one digit back
# (code[0:(i-1)] + 'X' interpretation).
n_new = n_current
# update n_prev and n_current
n_prev = n_current
n_current = n_new
return n_current
递归解决方案
int countdecodes(char * s)
{
int r = 0;
switch(*s)
{
case 0:
return 1;
case '0':
return 0;
case '1':
r = countdecodes(s+1);
if(*(s+1))
r = r + countdecodes(s+2);
return r;
case '2':
r = countdecodes(s+1);
switch(*(s+1))
{
case '0': case '1': case '2':
case '3': case '4': case '5':
case '6':
r = r + countdecodes(s+2);
default:
return r;
}
case '3': case '4': case '5': case '6':
case '7':case '8': case '9':
return countdecodes(s+1);
default:
return 0;
}
}
样品退货
对于这个具有 O(N) 时间复杂度和 O(1) 空间复杂度的问题，我有一个简单的基于模式的解决方案。
解释示例：-
12312
1
/ \
1,2 12
/ \ \
1,2,3 1,23 12,3
| | \
1,2,3,1 1,23,1 12,3,1
/ \ / \ / \
1,2,3,1,2 1,2,3,12 1,23,1,2 1,23,12 12,3,1,2 12,3,12
P1 P2 N T
1 0 1 1
1 1 2 2
2 1 2 3
3 0 1 3
3 3 2 6
P1 表示新元素不形成 2 位数字的案例数
P2 表示新元素形成 2 位数字的案例数
N=1 代表与 p1 相关的案例，N=2 代表与 p2 相关的案例
所以关于案例1和2的新树就像
1
/ \
1 2
/ \ \
1 2 1
| | |
1 1 1
/ \ / \ / \
1 2 1 2 1 2
#include <iostream>
#include <string>
using namespace std;
int decode(string s)
{
int l=s.length();
int p1=1;
int p2=0;
int n;
int temp;
for(int i=0;i<l-1;i++)
{
if(((int(s[i]-'0')*10)+int(s[i+1]-'0'))<=26)
{
n=2;
}
else
{
n=1;
}
temp=p2;
p2=(n==2)?p1:0;
p1=p1+t;
}
return p1+p2;
}
int main() {
string s;
getline(cin,s);
cout<<decode(s);
return 0;
}
它仅对从 1 到 9 的字符有效。
递归解决方案
list = []
def findCombiation(s,ls):
if len(s) == 0:
list.append(ls)
ls = ls + "0"
if s[0:1] == "0":
findCombiation(s[1:],ls)
else:
st = s[:2]
if st == "":
return
if int(st) > 25 :
findCombiation(s[1:],ls)
ls = ls + s[:1]
else:
findCombiation(s[1:],ls+s[:1])
findCombiation(s[2:],ls+s[:2])
findCombiation("99","")
print(set(list))
这是该问题的一个小而简单的O(n)解决方案，使用动态编程：
int ways(string s){
int n = s.size();
vector<int> v(n + 1, 1);
v[n - 1] = s[n - 1] != '0';
for(int i = n - 2; i >= 0; i--){
if(s[i] == '0') {v[i] = v[i + 1]; continue;}
if(s[i] <= '2' && s[i + 1] <= '6')
if(s[i + 1] != '0') v[i] = v[i + 1] + v[i + 2];
else v[i] = v[i + 2];
else v[i] = v[i + 1];
}
return v[0];
}
这个想法是逐个索引遍历。如果该索引（附加到下一个）包含小于或等于 26 且没有零的数字，则将其分为 2 种可能性，否则只有 1 种可能性。
ways("123"); //output: 3
ways("1230"); //output: 0
ways("1220"); //output: 2
ways("12321"); //output: 6
def nombre_codage(message):
map=[]
for i in range(1,27,1):
map.append(i)
nbr=1
n=len(message)
pair_couple=0
for j in range (0,n,2):
if int(message[j:j+2]) in map and len(message[j:j+2])==2:
pair_couple+=1
nbr+=2**pair_couple-1
impair_couple=0
for k in range (1,n,2):
if int(message[k:k+2]) in map and len(message[k:k+2])==2:
impair_couple+=1
nbr+=2**impair_couple-1
return nbr
这是 Python 中的一个解决方案，它将消息作为字符串，然后计算可以编码的两个数字的位数，并使用二项式系数——我使用了它的另一种形式(C(n-p)=2^n)——它计算可以对消息进行多少编码。