問題概要：
数字文字列（2〜9のみ）を入力として、該当するすべてのアルファベット組み合わせを返す。結果は任意の順序で出力可能。
電話ボタンの数字とアルファベットの対応関係は以下の通り（1は対応なし）：
2 -> "abc"
3 -> "def"
4 -> "ghi"
5 -> "jkl"
6 -> "mno"
7 -> "pqrs"
8 -> "tuv"
9 -> "wxyz"
例：input = "23" → ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] を返す。
解法アプローチ：
本問題は「バックトラッキング（再帰的探索）」アルゴリズムを用いて解く。全ての可能性を網羅するタイプの問題に最適。
処理フロー：
- 数字→文字の変換テーブルの構築：
- 数字と文字の対応関係をMap型で定義。
- 例：
2→"abc"、3→"def"。
- 再帰的探索の実装：
- 入力文字列の先頭から順に各数字に対応する文字を追加。
- 現在の組み合わせを
StringBufferで保持し、再帰呼び出し後に状態を戻す（バックトラック）。 - 入力文字列の末尾に達した時点で、現在の組み合わせを結果リストに追加。
- 終了条件：
- 再帰の深さが入力文字列の長さに達した場合、組み合わせを確定。
コード実装：
class PhoneNumberCombinator {
public List<String> generateCombinations(String inputDigits) {
List<String> results = new ArrayList<>();
if (inputDigits.isEmpty()) return results;
// 数字と文字のマッピングテーブル
Map<Character, String> digitMap = new HashMap<>();
digitMap.put('2', "abc");
digitMap.put('3', "def");
digitMap.put('4', "ghi");
digitMap.put('5', "jkl");
digitMap.put('6', "mno");
digitMap.put('7', "pqrs");
digitMap.put('8', "tuv");
digitMap.put('9', "wxyz");
// 探索開始
exploreCombinations(results, inputDigits, 0, digitMap, new StringBuffer());
return results;
}
private void exploreCombinations(List<String> results, String inputDigits, int position,
Map<Character, String> digitMap, StringBuffer current) {
// 終了条件：入力文字列の末尾に達した場合
if (position == inputDigits.length()) {
results.add(current.toString());
return;
}
char currentDigit = inputDigits.charAt(position);
String possibleChars = digitMap.get(currentDigit);
for (int i = 0; i < possibleChars.length(); i++) {
current.append(possibleChars.charAt(i));
exploreCombinations(results, inputDigits, position + 1, digitMap, current);
current.deleteCharAt(current.length() - 1); // バックトラック
}
}
}
実装詳細：
generateCombinationsメソッド：
- 入力が空文字の場合、空リストを返却。
- 数字と文字のマッピングテーブルを初期化。
- 探索を開始するため
exploreCombinationsメソッドを呼び出す。
exploreCombinationsメソッド：
positionは現在処理中の数字のインデックス。- 終了条件：
positionが入力文字列の長さに等しい場合、現在の組み合わせをリストに追加。 - 現在の数字に対応する文字を取得し、それぞれに対して再帰呼び出しを実行。
- 再帰呼び出しから戻る際、最後に追加した文字を削除して状態を戻す（バックトラック）。
計算量評価：
- 時間計算量：
O(4^n)（nは入力文字列の長さ、最大4文字の選択肢があるため） - 空間計算量：
O(n)（再帰スタックの深さ）＋O(4^n)（結果リストのサイズ）
まとめ：
- バックトラッキングアルゴリズムにより、すべての可能性を効率的に探索。
- 再帰とバックトラックの技術を用いて、組み合わせの生成を実現。
- 計算量は指数関数的だが、全組み合わせを求める問題には適した手法。