给定编码消息,计算可以解码的方式的数量

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"时,只需返回即可.

这个问题可以更有效地解决吗？

Answer 1

您当前对问题的近似是正确的.虽然,你需要非常小心,你正在处理所有不清楚的情况,这将使我的答案比需要的时间长一些.

查看此问题的正确方法是从动态编程的角度来看.让我们考虑你的输入字符串message和它的长度n.

要解码message的n字符,你需要在你有多少种方法解码知道message使用n - 1字符和message使用n - 2的字符.那是,

一个n字符的消息.

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

使用1位和message的n - 1字符.

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

使用长度为2位和1位message的n - 2字符.

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

现在,你可能会问自己:

如何在你有多少种方法解码计算message的n - 1人物和n - 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
  

decodeC中的迭代函数可能如下所示,

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

你可以在这里看到它.我正在使用恒定的额外内存进行计算.