【C++】電話番号の数字キーから生成できるすべての単語を出力する方法

問題概要

この記事では、与えられた数字列をもとに、昔ながらの携帯電話のテンキーでその数字を押したときに入力できるすべての単語(文字列の組み合わせ)を出力する方法を解説します。

現在広く使われているのはQWERTY配列のキーボードですが、スマートフォンが普及する以前の携帯電話には、12個のボタンからなるテンキーが搭載されていました。各ボタンには数字とアルファベットの両方が割り当てられており、たとえば「6」のキーには「MNO」が対応していて、キーを1回・2回・3回と押すことでそれぞれ「M」「N」「O」を入力できました。

当時のキーパッドの配置は以下の通りです。

このキーパッドにはすべてのアルファベットが割り当てられているため、ユーザーは任意の単語を入力できます。本問題では、与えられた数字列から生成可能なすべての単語の組み合わせを出力します。

具体的な例を使って問題を確認してみましょう。

入力: 687
出力: MTP, MTQ, MTR, MTS, MUP, MUQ, MUR, MUS, MVP, MVQ,
MVR, MVS, NTP, NTQ, NTR, NTS, NUP, NUQ, NUR, NUS, NVP, NVQ,
NVR, NVS, OTP, OTQ, OTR, OTS, OUP, OUQ, OUR, OUS, OVP, OVQ,
OVR, OVS

解き方のアプローチ

上記の出力例からパターンを読み取ってみましょう。各数字キーには固有の文字セットが割り当てられており、入力時にはそれらの文字を使用します。つまり、1桁あたり最大4つの選択肢が存在します(「7」と「9」の場合)。この性質を利用して、1桁ずつ文字を固定しながら残りの桁の組み合わせを再帰的に生成することで、すべての単語を網羅的に列挙できます。

それでは、再帰を使ってこの考え方を実装するプログラムを見ていきましょう。

C++での実装例

#include <iostream>
#include <string.h>
using namespace std;
const char keypad[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz"};
void printWords(int number[], int curr_digit, char output[], int n){
   int i;
   if (curr_digit == n){
      cout<<output<<" ";
      return ;
   }
   for (i=0; i<strlen(keypad[number[curr_digit]]); i++){
      output[curr_digit] = keypad[number[curr_digit]][i];
      printWords(number, curr_digit+1, output, n);
      if (number[curr_digit] == 0 || number[curr_digit] == 1)
         return;
   }
}
int main(void){
   int number[] = {6,8,7};
   cout<<"The output character formed is : \n";
   int n = sizeof(number)/sizeof(number[0]);
   char result[n+1];
   result[n] ='\0';
   printWords(number, 0, result, n);
   return 0;
}

実行結果

プログラムの出力は以下の通りです。

mtp mtq mtr mts mup muq mur mus mvp mvq mvr mvs ntp ntq ntr nts
nup nuq nur nus nvp nvq nvr nvs otp otq otr ots oup ouq our ous ovp
ovq ovr ovs

コードの解説

このプログラムの動作のポイントは以下の通りです。

• keypad配列: 各数字(0〜9)に対応するアルファベットを格納した2次元配列です。「0」と「1」には文字が割り当てられていません。
• printWords関数: 現在処理中の桁(curr_digit)に対応する各文字を順番に出力バッファへ設定し、次の桁へ再帰的に処理を進めます。
• 終了条件: curr_digitが桁数nに達した時点で、完成した1つの単語が出力されます。
• 0と1の扱い: 対応する文字が存在しないため、その時点で再帰を打ち切ります。

計算量についても触れておきます。各桁に最大4つの選択肢があるため、n桁の数字列から生成される単語の総数は最大でO(4ⁿ)となります。指数関数的に増加するため、桁数が大きくなると出力件数が急激に膨らむ点には注意が必要です。