C/C++で電話番号のダイヤルに使える文字列の全組み合わせを出力する方法

問題の概要

ある番号が与えられたとき、以下の仕様に基づいて、その番号を電話でダイヤルするために使用できる文字列のすべての組み合わせを表示するプログラムを考えます。

• 2 →「A」「B」「C」のいずれか
• 3 →「D」「E」「F」のいずれか
• ……（以下同様）
• 7 →「P」「Q」「R」「S」のいずれか
• 8 →「T」「U」「V」のいずれか
• 9 →「W」「X」「Y」「Z」のいずれか
• 1 →「1」のみ
• 0 →「0」のみ

例として、電話番号として「89」が与えられた場合、プログラムは次の12通りの文字列を出力します。

TW TX TY TZ UW UX UY UZ VW VX VY VZ

アルゴリズムの考え方

この問題は再帰を使って解くのが一般的です。各桁について対応する文字候補を順に選びながら、次の桁へと処理を進めていきます。最後の桁まで文字を選び終えた時点で1つの文字列が完成したことになるため、それを出力します。

1. 各数字に対応する文字をハッシュテーブル（TableHash）にあらかじめ格納しておく。
2. 現在の桁に対応する文字を1つ選び、出力用バッファに設定する。
3. 次の桁に対して同じ処理を再帰的に繰り返す。
4. すべての桁の処理が完了したら、完成した文字列を出力する。

C言語での実装例

#include <stdio.h>
#include <string.h>

/* TableHash[i] には、電話の数字 i に対応する文字が格納される */
const char TableHash[10][5] = {
    "0", "1", "ABC", "DEF", "GHI",
    "JKL", "MNO", "PQRS", "TUV", "WXYZ"
};

/* 再帰関数：入力された数字列 number1[]（サイズ n1）から
   作成できるすべての単語を出力する。
   完成した単語は output1[] に1つずつ格納される */
void UtilWordsPrint(int number1[], int curr_digit1, char output1[], int n1)
{
    int i;

    /* ベースケース：出力すべき単語が完成した場合 */
    if (curr_digit1 == n1) {
        printf("%s ", output1);
        return;
    }

    /* 現在の桁に対して考えられるすべての文字を試し、
       残りの桁について再帰的に処理する */
    for (i = 0; i < strlen(TableHash[number1[curr_digit1]]); i++) {
        output1[curr_digit1] = TableHash[number1[curr_digit1]][i];
        UtilWordsPrint(number1, curr_digit1 + 1, output1, n1);
    }
}

/* UtilWordsPrint() のラッパー関数。
   出力用配列 result1 を作成し、UtilWordsPrint() を呼び出す */
void printWords(int number1[], int n1)
{
    char result1[n1 + 1];
    result1[n1] = '\0';
    UtilWordsPrint(number1, 0, result1, n1);
}

/* ドライバプログラム */
int main(void)
{
    int number1[] = {8, 9};
    int n1 = sizeof(number1) / sizeof(number1[0]);
    printWords(number1, n1);
    return 0;
}

出力結果

TW TX TY TZ UW UX UY UZ VW VX VY VZ

コードのポイント

• TableHash は、数字ごとに割り当てられた文字を参照するためのテーブルです。配列のインデックスがそのままダイヤルの数字に対応します。
• UtilWordsPrint() は再帰的に動作し、現在の桁を示す curr_digit1 が桁数 n1 に達した時点で1つの文字列が完成したと判断して出力します。
• printWords() はヌル終端文字を含む出力用バッファを確保し、再帰関数への入り口となるラッパー関数です。
• 「1」と「0」はそれぞれ自分自身にのみマッピングされるため、テーブル上では1文字だけを持つ扱いとなり、特別な分岐を設けなくても自然に処理されます。

計算量

このコードの時間計算量は O(4ⁿ) です。ここで n は入力番号の桁数を表します。これは、1つの数字に最大4文字（「7」と「9」の場合）が割り当てられるため、最悪の場合に各桁で4通りの選択肢が生じることに起因します。一方、空間計算量は再帰の深さと出力バッファのサイズに比例し、O(n) となります。