给定一个编码信息，计算它可以被解码的方式数量。

Question

你将得到一个只包含数字的编码信息。你还会得到以下映射：

 A : 1
 B : 2
 C : 3
 ..
 Z : 26

给定一个编码消息，计算它可以被解码的方式数。

例如：12 可以有两种解码方式：(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时，只需返回。这个问题有更高效的解决方法吗？

- poorvank

---

编码方法不清楚。例如，在编码方法中，如何将“1”与“11”分别定义？ - suspectus

根据所提供的映射，A->1..而K->11..因此，解码数字11的方式有2种（A,A对应1,1）和（k对应数字11）。 - poorvank

@poorvank，根据我所读的，你似乎还没有计算任何东西。 - Alexander

Answer 1

您对这个问题的当前近似方法是正确的。尽管如此，您需要非常小心地处理所有不清楚的情况，这将使我的答案比所需的要长一些。

从动态规划的角度来看，这个问题的正确方法是这样的。让我们把您的输入字符串称为message，它的长度为n。

要解码一个由n个字符组成的message，您需要知道使用n-1个字符和使用n-2个字符的message可以有多少种方式进行解码。也就是说，

一个由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 |
        +---+---+---+---+---+---+---+---+---+---+---+

使用一个数字和一个长度为 n-1 的消息。涉及编程相关内容。请保留 HTML 标签。

                                              1
          1   2   3   4   5   6   7   8   9   0       1
        +---+---+---+---+---+---+---+---+---+---+   +---+
message | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 4 | 1 | + | 2 |
        +---+---+---+---+---+---+---+---+---+---+   +---+

使用两个数字和一个长度为 n-2 的消息。保留 HTML 标签。

                                                  1
          1   2   3   4   5   6   7   8   9       0   1
        +---+---+---+---+---+---+---+---+---+   +---+---+
message | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 4 | + | 1 | 2 |
        +---+---+---+---+---+---+---+---+---+   +---+---+

现在，您可能会问自己：

如何计算出解码n-1个字符和n-2个字符的消息的方式数量？

实际上方法是一样的。 最终，您将将其缩小到基本情况。

假设ways[n]是解码n个字符的消息的方式数。然后，可以这样放置ways[n]，

ways[n] = ways[n - 1] + ways[n - 2]

由于没有线索来定义空字符串的方式数量，我将其视为1。

在适当的约束条件和基本情况下，

• n = 0,

   ways[n] =  1
  

• n > 1 and message[n] is valid and message[n - 1:n] is valid,

   ways[n] = ways[n - 1] + ways[n - 2]
  

• n > 1 and message[n] is valid and message[n - 1:n] is not valid,

   ways[n] = ways[n - 1]
  

• n > 1 and message[n] is not valid and message[n - 1:n] is valid,

   ways[n] = ways[n - 2]
  

• otherwise,

   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上看到它。 我为计算使用了恒定的额外内存。

- Alexander

---

什么是message[n]有效和message[n-1:n]有效的意思？ - j will

尝试解码('22', 2) -> 将会给出一个无效的答案。 - nml

在“消息”图表中，上面的数字代表什么？它们是数组索引吗？如果是这样，我认为可能存在错误。您跳过了7。 - 425nesp

“正确”的单词应该被替换。这是用动态规划解决这个问题的一种方式。一个人可能会被误导，因为它看起来像是唯一的解决方案。我会说“最优解”。另一种方法是采用O(2^n)暴力破解。 - Michał Dobi Dobrzański

w 应该在 for 循环内部声明，这样会更易读。 - Michał Dobi Dobrzański

Answer 2

我想用我的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

- James Baye

Answer 3

递归解决方案

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))

- smit kadvani

Answer 4

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)--来计算您可以编码消息的方式数量。

- MajesticPanda

---

我认为这个答案不正确，测试用例"9101727"应该只有两种解码方式，分别是[9-10-1-7-2-7]和[9-10-17-2-7]，而输出结果为5，这是错误的。 - MYaser

Answer 5

递归解决方案

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;
    }
}

示例返回

1. countdecodes("123"); // 返回 3
2. countdecodes("1230"); // 返回 0
3. countdecodes("1220"); // 返回 2
4. countdecodes("12321"); // 返回 6

- user93353

---

为什么要踩我？谁踩了请在评论区写下原因。 - user93353

为什么又被踩了？请在评论中说明原因。程序完美无缺地运行着。我真的很想知道有人发现这个答案有什么问题。 - user93353

@user93353 你尝试过使用长输入测试这个解决方案吗？虽然它可能完美地工作，但由于它运行时间呈指数增长，因此它不是一个可接受的解决方案。 - maxx777

Answer 6

我对这个问题有一个基于简单模式的解决方案，时间复杂度为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代表新元素不形成两位数的情况数

P2代表新元素形成两位数的情况数

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有效。

- knupd1337

Answer 7

这是一个使用动态规划的小而简单的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且没有零的数字，则分为两种可能性，否则只有一种。

ways("123");    //output: 3
ways("1230");   //output: 0
ways("1220");   //output: 2
ways("12321");  //output: 6

- Daniel