C#のバックトラッキングでスマートフォンキーパッドの全文字組み合わせを取得する方法

電話番号のキーパッド（2〜9）に対応する文字の組み合わせをすべて求める問題は、より小さく単純な「部分問題」に分割して考えることができます。各数字を1つずつ順番に処理し、それぞれの数字から到達可能な文字をマップ（Dictionary）に格納しておきます。そして、組み合わせの長さが入力された桁数に達した時点で、その結果をカウント・記録していきます。

アプローチのポイント

この種の問題は「バックトラッキング（探索の巻き戻し）」と呼ばれる手法で効率的に解くことができます。具体的な流れは以下の通りです。

• 各数字に対応する文字のマッピングをDictionaryで定義する
• 先頭の数字から順に、対応する各文字を現在の組み合わせに追加しながら再帰呼び出しを行う
• 残りの数字がなくなった時点で、完成した組み合わせを出力リストに追加する

サンプルコード

using System;
using System.Collections.Generic;

namespace ConsoleApplication {
    public class BackTracking {
        private string GetKeyPadValueBasedOnInput(string digit) {
            Dictionary<string, string> keypad = new Dictionary<string, string>();
            keypad.Add("2", "abc");
            keypad.Add("3", "def");
            keypad.Add("4", "ghi");
            keypad.Add("5", "jkl");
            keypad.Add("6", "mno");
            keypad.Add("7", "pqrs");
            keypad.Add("8", "tuv");
            keypad.Add("9", "wxyz");
            return keypad.GetValueOrDefault(digit);
        }

        public void FindSequence(string currentList, string digits, List<string> output) {
            if (digits.Length == 0) {
                output.Add(currentList);
                return;
            } else {
                string digit = digits.Substring(0, 1);
                string letters = GetKeyPadValueBasedOnInput(digit);
                for (int i = 0; i < letters.Length; i++) {
                    char letter = GetCharFromString(letters, i);
                    FindSequence(currentList + letter, digits.Substring(1), output);
                }
            }
        }

        private char GetCharFromString(string letters, int value) {
            char[] charArr = letters.ToCharArray();
            return charArr[value];
        }
    }

    class Program {
        static void Main(string[] args) {
            BackTracking b = new BackTracking();
            List<string> output = new List<string>();
            b.FindSequence("", "34", output);
            foreach (var item in output) {
                Console.WriteLine(item);
            }
        }
    }
}

実行結果

dg
dh
di
eg
eh
ei
fg
fh
fi

コードの解説

この例では、入力として「34」を渡しています。「3」には d・e・f の3文字、「4」には g・h・i の3文字が割り当てられているため、3×3＝9通りの組み合わせが出力されます。

処理の流れを簡単に整理すると次のようになります。

1. GetKeyPadValueBasedOnInputメソッド： 数字に対応する文字列をDictionaryから取得します。
2. FindSequenceメソッド： 再帰的に呼び出され、残りの数字が空になったタイミングで組み合わせを確定させます。
3. Mainメソッド： 結果リストを受け取り、コンソールにすべての組み合わせを出力します。

なお、入力の桁数が増えると組み合わせの総数は指数関数的に増加します（各桁あたり最大4文字のため）。そのため、実用的な用途では入力桁数に上限を設けるか、結果を逐次処理する設計を検討するとよいでしょう。