JavaScriptで解く！エンコードされたメッセージのデコード可能な組み合わせ数を求めるアルゴリズム

アルファベットを a = 1、b = 2、…、z = 26 という対応関係で数値にマッピングすることを考えます。ここで、あるエンコードされたメッセージが与えられ、そのメッセージをデコードできる方法が何通りあるかを数えるJavaScript関数を作成する必要があります。

例えば、メッセージ「111」の場合、答えは 3 になります。これは次の3通りにデコードできるためです。

• 1・1・1 → a・a・a（「aaa」）
• 11・1 → k・a（「ka」）
• 1・11 → a・k（「ak」）

サンプルコード

この問題を解くコードは以下の通りです。

const waysToProcess = ( message, ways = 0 ) => {
   if ( message.length ) {
      ways = waysToProcess( message.slice( 1 ,message.length), ways );
      const numCurr = parseInt( message[0] );
      const numNext = "undefined" === typeof message[1] ? null :
      parseInt(message[1]);
      if ( numCurr && numNext
         && numCurr < 3
         && ( numCurr + numNext ) < 27
      ) {
         ways = waysToProcess( message.slice( 2 ,message.length), ways );
      }
   } else {
      ways++;
   }
   return ways;
}
console.log(waysToProcess('111'));

出力結果

コンソールには以下のように出力されます。

3

コードの解説

この関数は再帰処理によって動作します。処理の流れは次のとおりです。

1. メッセージが空でない場合、先頭の1文字を1つのアルファベットとして扱い、残りの文字列に対して再帰的に関数を呼び出します。
2. さらに、先頭の2文字が「10〜26」の範囲に対応できる場合（先頭が1または2で、合計が27未満）、2文字をまとめて1つのアルファベットとしてデコードできるため、そのパターンについても再帰的に探索します。
3. メッセージが空になった時点で、それが1つの完全なデコード方法としてカウントされます。

このように、1文字ずつのデコードと2文字まとめのデコードを組み合わせて全パターンを探索することで、デコード可能な組み合わせの総数を求めることができます。