[Java] LeetCode 17번 Letter Combinations of a Phone Number

옛날 피처폰에 숫자위치에 있는 알파벳들의 가능한 조합을 모두 출력하는 문제이다. 

이런 조합의 문제에서는 재귀호출을 통해서 쉽게 해결할 수 있다.

재귀 함수를 작성할 때 중요한 포인트는 언제 함수가 종료되는지 잘 명시하는 것이다. digits의 길이가 0이 되면 비어있는 리스트를 리턴하고, 1이라면 map에서 조회하여 리턴한다. 

이외의 경우에는 첫번째 숫자와 나머지 문자를 이어서 정답에 추가하여 리턴한다.

class Solution {
    Map<String, List<String>> map = new HashMap<>();
    {
        map.put("2", List.of("a", "b", "c"));
        map.put("3", List.of("d", "e", "f"));
        map.put("4", List.of("g", "h", "i"));
        map.put("5", List.of("j", "k", "l"));
        map.put("6", List.of("m", "n", "o"));
        map.put("7", List.of("p", "q", "r", "s"));
        map.put("8", List.of("t", "u", "v"));
        map.put("9", List.of("w", "x", "y", "z"));
    }

    public List<String> letterCombinations(String digits) {
        List<String> answer = new ArrayList<>();
        if (digits.length() == 0) {
            return answer;
        } else if (digits.length() == 1) {
            return map.get(digits);
        }
        String digit = digits.substring(0, 1);
        List<String> str = this.map.get(digit);
        List<String> rightStr = letterCombinations(digits.substring(1));
        for (int i = 0; i < str.size(); i++) {
            String s = str.get(i);
            for (int j = 0; j < rightStr.size(); j++) {
                String rs = rightStr.get(j);
                answer.add(s + rs);
            }
        }
        return answer;
    }
}