릿코드 Letter Combinations of a Phone Number

2021-01-08

1. 릿코드 Letter Combinations of a Phone Number

2. 문제

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.

2.1. Example 1:

Input: digits = “23”
Output: [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

2.2. Example 2:

Input: digits = “”
Output: []

2.3. Example 3:

Input: digits = “2”
Output: [“a”,“b”,“c”]

2.4. Constraints:

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

2.1. 컴퓨팅적 사고

패드에서 누를 수 있는 모든 번호의 패드리스트를 하나 생성시킵니다.
해당 주어진 패드의 정보를 가지고 DFS를 수행합니다. 예를 들어 이 들어왔다면
2->3번을 누를시에 갈수 있는 모든 경우를 찾아줍니다.

Test Case

예를 들면 23의 패드가 들어와서 해당 패드 영문자가 눌렸다고 가정할때 abc / def 가 있다고 가정할때 아래 처럼 나타낼 수 있습니다.

a -> d, a -> e, a -> f
b -> d, b -> e, b -> f
c -> d, c -> e, c -> f

해당 형식으로 방문하고 체크합니다.
DFS의 Basement조건은 digits 길이만큼 선택될 수 있기때문에 해당 조건일때 해당 값까지 쌓인 문자열을 answer 리스트에 넣어주고 DFS를 수행하던것을 종료시킵니다. 그러면 현재까지 생성된 모든 조합을 출력시킬 수 있습니다.

2.2. 소스코드

public class leetcode_letter_combinations_of_a_phone_number_kgh {
    static String[] padList = {"abc","def","ghi","jki","mno","pqrs","tuv","wxyz"};
    static List<String> answer = new ArrayList<>();
    public static void main(String[] args) {
        letterCombinations("23");
    }
    static void letterCombinations(String digits) {
        if(digits.length() == 0){
            System.out.println(answer);
        }
        dfs(digits,0, "");
        answer.forEach(v-> System.out.println(v));
    }
    private static void dfs(String digits, int cnt, String str) {
        if(cnt == digits.length()){
            answer.add(str);
            return;
        }
        String padArr = padList[(digits.charAt(cnt)-'0')-2];
        System.out.println(padArr);
        for(char c : padArr.toCharArray()){
            System.out.println("dfs("+digits+","+(cnt+1)+","+(str+c)+")");
            dfs(digits, cnt+1,str+c);
        }
    }
}

Algorithmleetcode