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」でないかどうかを確認し、trueの場合は、0から長さ-1までの文字列の残りの部分を確認します。最後の2桁の文字列部分が1〜26の数値になるかどうかを確認します。trueの場合は、カウントを更新し、残りの文字列が0〜2の長さになるかどうかを確認します。

• 入力を文字列str[]として取得しています。

• 関数decode_digit_seq（char * str、int length）は、文字列とその長さを受け取り、strの可能なデコードの数を返します。

• 長さが0の場合。1を返します。

• 長さが1の場合。1を返します。

• 最後の1文字がゼロ以外の場合、カウントはdecode_digit_seq（str、int length-1）

  になります。

• 最後から2番目の文字が1の場合、最後の2桁は10から19（JからS）の間になり、カウントをcount =count + decode_digit_seq（str、length-2）

  として更新します。

• 最後から2番目の文字が2で、最後の文字が7未満の場合、最後の2桁は20〜26（T〜Z）になり、カウントをcount =count + decode_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