Letter Combinations of a Phone Number

🔗 문제 링크

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

🔍 문제 설명

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'].$

---

🗝 풀이 (언어 : Java)

앞의 문제들을 풀고 응용해서 혼자서 풀 수 있었다. 반복문 안에서 다음 위치 인덱스를 i+1로 주어야하는데 자꾸 idx+1로 헷갈려서 문제였다. 감은 조금 잡은 것 같은데 이런 유형에 자신감을 가지려면 좀 더 만나봐야 할 것 같다.

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

class Solution {
    private void dfs(List<String> answer, Map<Character, char[]> map, String digits, String word, int idx) {
        // 개수가 다차서 단어가 완성되면 정답 리스트에 넣기
        if (word.length() == digits.length())
            answer.add(word);
        // 해당 글자의 알파벳 배열에서 한글자씩 골라서 모든 경우의 수 단어를 만든다
        for (int i = idx; i < digits.length(); i++) {
            char[] alphabet = map.get(digits.charAt(i));
            for (char a : alphabet)
                dfs(answer, map, digits, word + a, i + 1);
        }
    }

    public List<String> letterCombinations(String digits) {
        List<String> answer = new ArrayList<>();
        // 숫자별 알파벳 정의
        Map<Character, char[]> map = Map.of(
                '2', new char[]{'a', 'b', 'c'},
                '3', new char[]{'d', 'e', 'f'},
                '4', new char[]{'g', 'h', 'i'},
                '5', new char[]{'j', 'k', 'l'},
                '6', new char[]{'m', 'n', 'o'},
                '7', new char[]{'p', 'q', 'r', 's'},
                '8', new char[]{'t', 'u', 'v'},
                '9', new char[]{'w', 'x', 'y', 'z'}
        );
        // 숫자 아무것도 안누르는 경우 예외처리
        if (digits.equals(""))
            return answer;
        dfs(answer, map, digits, "", 0);
        return answer;
    }
}