문제

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

제한사항

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9']

접근

문자열로 된 숫자가 주어졌을 때, 핸드폰 메시징 방법을 통해 만들 수 있는 문자열 조합을 반환하는 문제입니다. 전제 조건은,

1. 숫자로만 구성된 파라미터
2. 출력 가능한 모든 조합을 구하되, 순서는 상관 없음
3. 문자를 출력할 수 없는 숫자는 주어지지 않음(ex. 1, 0, *, #)

그림이 주어져서 쉽게 접근할 수 있었어요. 2는 abc, 3은 def...식으로 문자를 칠 수 있고 해당 전제는 모두 컨테이너에 담았고, 모든 경우의 수를 접근해야 했기에 DFS 방식으로 풀이했습니다.

답안

import java.util.ArrayList;
import java.util.List;

class Solution { 
    List<String> characters = new ArrayList<>(10);

    void dfs(String digits, String msg, List<String> answer){
        if(msg.length() == digits.length()){
            answer.add(msg);
            return;
        }

        int nextDigit = Integer.parseInt("" + digits.charAt(msg.length()));
        String nextDigitChars = characters.get(nextDigit);
        for(int i = 0; i < nextDigitChars.length(); ++i){
            char alphabet = nextDigitChars.charAt(i);
            dfs(digits, msg + alphabet, answer);
        }
    }

    public List<String> letterCombinations(String digits) {
        List<String> answer = new ArrayList<>();
        if(digits.length() == 0)
            return answer;
        
        characters.add("");characters.add("");
        characters.add("abc");
        characters.add("def");
        characters.add("ghi");
        characters.add("jkl");
        characters.add("mno");
        characters.add("pqrs");
        characters.add("tuv");
        characters.add("wxyz");
        dfs(digits, "", answer);
        return answer;
    }
}