计算C ++中给定数字序列的可能解码

我们得到了一个代表数字序列的字符串。每个数字从1到26解码为英文字母。1是“ A”，2是“ B”，依此类推直到26为“ Z”。目的是找到给定数字序列之外所有可能解码的计数。如果序列是“ 123”，则可能的解码是“ ABC”(1-2-3)，“ LC”(12-3)，“ AW”(1-23)。数是3。

让我们通过示例来理解。

输入− str [] =“ 1532”

输出-给定数字序列的可能解码计数为-2

说明-可能的解码为AECB-(1-5-3-2)和OCB(15-3-2)。

输入− str [] =“ 216”

输出-给定数字序列的可能解码计数为-3

解释-可能的解码为“ BAF”(2-1-6)，“ UF”(21-6)，“ BP”(2-16)

以下程序中使用的方法如下

我们将使用递归方法进行此操作。将字符串的一部分传递给此递归方法。

如果最后一个数字不为“ 0”，则检查是否为真，请检查字符串的其余部分，介于0和length-1之间。检查最后两位数字的字符串部分是否使数字介于1和26之间。如果为true，则更新count并检查字符串的其余部分（介于0和length-2之间）。

• 我们将输入作为字符串str []。

• 函数decode_digit_seq（char * str，int length）获取字符串及其长度，并返回可能的str解码计数。

• 如果length为0。返回1。

• 如果length为1，则返回1。

• 如果最后一个字符不为零，则计数为decode_digit_seq（str，int length-1）

• 如果倒数第二个字符是1，则后两位数字将在10到19之间（从J到S），将count更新为count = count + encode_digit_seq(str,length-2)

• 如果倒数第二个字符是2并且最后一个字符<7，则后两位数将在20到26之间（从T到Z），更新计数为count = count + encode_digit_seq(str,length-2)

• 现在所有案例都被处理了。

• 最后，所有递归返回结果。

示例

#include <iostream>
#include
using namespace std;
int decode_digit_seq(char *str, int length){
   int count = 0;
   if(length == 0){
      return 1;
   }
   if(length == 1){
      return 1;
   }
   if(str[0] == '0'){
      return 0;
   }
   if(str[length-1] > '0'){
      count = decode_digit_seq(str, length-1);
   }
   if(str[length-2] == '1'){
      count = count + decode_digit_seq(str, length-2);
   }
   if(str[length-2] == '2' && str[length-1] < '7'){
      count = count + decode_digit_seq(str, length-2);
   }
   return count;
}
int main(){
   char str[] = "7651";
   int length = strlen(str);
   cout<<"Count of Possible Decodings of a given Digit Sequence are: "<< decode_digit_seq(str, length);
   return 0;
}

输出结果

如果我们运行上面的代码，它将生成以下输出-

Count of Possible Decoding of a given Digit Sequence are: 1