C++で数字列の可能なデコード数を求める方法

問題の概要

数字の並びを表す文字列が与えられます。各数字は1から26までの英字アルファベットに対応してデコードされます。つまり、1は「A」、2は「B」、…、26は「Z」という対応関係です。この記事の目的は、与えられた数字列から作り出せるすべてのデコードの組み合わせの数を求めることです。

例えば、数字列が「123」の場合、可能なデコードは「ABC」(1-2-3)、「LC」(12-3)、「AW」(1-23) の3通りとなり、答えは3になります。

例で理解しましょう

入力 − str[]="1532"

出力 − 与えられた数字列の可能なデコードの数 − 2

説明 − 可能なデコードは AECB (1-5-3-2) と OCB (15-3-2) の2通りです。

入力 − str[]="216"

出力 − 与えられた数字列の可能なデコードの数 − 3

説明 − 可能なデコードは「BAF」(2-1-6)、「UF」(21-6)、「BP」(2-16) の3通りです。

プログラムで使用するアプローチ

ここでは再帰的な手法を用いて問題を解きます。文字列の一部分を再帰関数に渡しながら処理を進めていきます。

まず、末尾の1桁が「0」でないかを確認します。「0」でなければ、先頭から length-1 文字分の残りの文字列について再帰的に調べます。さらに、末尾の2桁が 1〜26 の範囲の数値として有効である場合は、カウントを更新し、先頭から length-2 文字分の残りの文字列についても再帰的に調べます。

• 入力として文字列 str[] を受け取ります。
• 関数 decode_digit_seq(char *str, int length) は、文字列とその長さを受け取り、その数字列の可能なデコードの総数を返します。
• length が 0 の場合は 1 を返します。
• length が 1 の場合も 1 を返します。
• 末尾の1文字が「0」以外であれば、count = decode_digit_seq(str, 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) としてカウントを更新します。
• これにより、すべてのケースが網羅されます。
• 最後に、すべての再帰呼び出しが完了した時点で count を結果として返します。

サンプルコード

#include <iostream>
#include <cstring>
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