17. Letter Combinations of a Phone Number

문제

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

제한사항

풀이

    import java.util.*;

    class Solution {
        public List<String> letterCombinations(String digits) {
            
            Map<Character, List<String>> map = new HashMap<>();
            
            if(digits.equals("")) return new ArrayList<>();
            map.computeIfAbsent('2', k-> List.of("a", "b", "c"));
            map.computeIfAbsent('3', k-> List.of("d", "e", "f"));
            map.computeIfAbsent('4', k-> List.of("g", "h", "i"));
            map.computeIfAbsent('5', k-> List.of("j", "k", "l"));
            map.computeIfAbsent('6', k-> List.of("m", "n", "o"));
            map.computeIfAbsent('7', k-> List.of("p", "q", "r", "s"));
            map.computeIfAbsent('8', k-> List.of("t", "u", "v"));
            map.computeIfAbsent('9', k-> List.of("w", "x", "y", "z"));
            List<String> answer = new ArrayList<>();
            backtracking(map, digits, 0, new StringBuilder(), answer);

            return answer; 
        }

        private void backtracking(
            Map<Character,List<String>> map, String digits, int offset, StringBuilder comb,
            List<String> answer) {
                if(offset == digits.length()) {
                    answer.add(comb.toString());
                    return;
                }

                for(String l : map.get(digits.charAt(offset))) {
                    comb.append(l);
                    backtracking(map, digits, offset+1, comb, answer);
                    comb.deleteCharAt(comb.length()-1);
                }
        }
    }

회고

숫자에 여러 알파벳이 매칭되어 있다. 숫자 조합이 입력으로 주어지고 숫자 조합으로 만들 수 있는 모든 알파벳 조합을 구하는 문제였다. dfs를 활용하여 문제를 해결하였다. 

1. offset이 digits 길이가 되었을 때, answer에 알파벳 조합을 추가한다(add).

2. 알파벳 조합(comb)을 업데이트할 때, 다음 조합을 고려해서 backtracking이 끝나면, 추가했던 알파벳을 제거하는 작업을 포함한다.

for(String l : map.get(digits.charAt(offset))) {
                    comb.append(l);
                    backtracking(map, digits, offset+1, comb, answer);
                    comb.deleteCharAt(comb.length()-1);
                }