バックトラッキング
入力には 2 から 9 までの数字が与えられます。それぞれの数字は電話のキーパッド上の文字に直接対応します。入力が空の場合、作れる組み合わせはないため空のリストを返します。
再帰では数字を1桁ずつ処理します。インデックス i の呼び出しに入った時点で、StringBuilder には先頭から i 個の数字に対して選んだ文字が、それぞれ1文字ずつ順番に格納されている、というのが不変条件です。現在の数字に対応する各文字について、文字を追加して次のインデックスを再帰呼び出しし、次の文字を試す前に追加した文字を削除します。深さが N に達すると、接頭辞には入力の各数字に対する文字が1文字ずつそろっているので、完成した組み合わせとして保存します。
組み合わせ数は最大で 4^N であり、完成した文字列のコピーにはそれぞれ O(N) 時間がかかるため、出力サイズを考慮した最悪時の時間計算量は O(N * 4^N) です。出力リストを除くと、ビルダーと再帰呼び出しスタックに必要な補助領域は O(N) です。
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
private static final String[] KEYPAD = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public List<String> letterCombinations(String digits) {
List<String> answer = new ArrayList<>();
if (digits.isEmpty()) {
return answer;
}
backtrack(digits, 0, new StringBuilder(), answer);
return answer;
}
private void backtrack(String digits, int index, StringBuilder prefix, List<String> answer) {
if (index == digits.length()) {
answer.add(prefix.toString());
return;
}
String letters = KEYPAD[digits.charAt(index) - '0'];
for (int i = 0; i < letters.length(); i++) {
prefix.append(letters.charAt(i));
backtrack(digits, index + 1, prefix, answer);
prefix.deleteCharAt(prefix.length() - 1);
}
}
}