forked from onlybooks/java-algorithm-interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathP36_1.java
More file actions
47 lines (41 loc) · 1.69 KB
/
P36_1.java
File metadata and controls
47 lines (41 loc) · 1.69 KB
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package ch12;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class P36_1 {
public void dfs(List<String> result, Map<Character, List<Character>> dic, String digits, int index, StringBuilder path) {
// 끝까지 탐색했으면 결과를 저장하고 리턴
if (path.length() == digits.length()) {
result.add(String.valueOf(path));
return;
}
// 현재 자리 숫자에 해당하는 모든 문자열 탐색
for (Character c : dic.get(digits.charAt(index))) {
// 현재 자리 +1, 지금까지 구성된 문자열 path 이용 재귀 DFS
dfs(result, dic, digits, index + 1, new StringBuilder(path).append(c));
}
}
public List<String> letterCombinations(String digits) {
// 결과 저장 리스트 선언
List<String> result = new ArrayList<>();
// 예외 처리
if (digits.length() == 0)
return result;
// 번호로 조합 가능한 문자 목록 구성
Map<Character, List<Character>> dic = new HashMap<>();
dic.put('0', List.of());
dic.put('1', List.of());
dic.put('2', List.of('a', 'b', 'c'));
dic.put('3', List.of('d', 'e', 'f'));
dic.put('4', List.of('g', 'h', 'i'));
dic.put('5', List.of('j', 'k', 'l'));
dic.put('6', List.of('m', 'n', 'o'));
dic.put('7', List.of('p', 'q', 'r', 's'));
dic.put('8', List.of('t', 'u', 'v'));
dic.put('9', List.of('w', 'x', 'y', 'z'));
// 현재 자리 0, 빈 문자열 이용 DFS 시작
dfs(result, dic, digits, 0, new StringBuilder());
return result;
}
}