LeetCode: 17. Letter Combinations of a Phone Number

LeetCode: 17. Letter Combinations of a Phone Number

숫자 문자열 digits(2–9) 가 주어지면, 전화 키패드 매핑에 따라 만들 수 있는 모든 문자 조합을 구하는 문제입니다.
예를 들어 "23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"].

이 글에서는 접근 방식(아이디어) → 코드 구조 → 시간/공간 복잡도 → 엣지 케이스 → 대안 풀이(BFS) 순서로 정리합니다. 마지막에 디버깅 팁과 테스트 케이스도 넣었습니다.

---

문제 핵심 요약

• 각 숫자(2–9)는 문자 집합에 매핑됨:
  2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz
• 목표: 각 자리에서 문자 1개씩 골라 모든 길이 digits.length()의 문자열 생성
• 본질적으로 카테시안 곱(Cartesian Product) 문제이며, 백트래킹(DFS) 으로 자연스럽게 풀린다.

---

접근 방식: 백트래킹(DFS)

백트래킹의 3단계 패턴:

1. 선택: 현재 자리(index)의 숫자에 대응하는 문자 중 하나를 current에 추가
2. 탐색: 다음 자리(index+1)로 재귀 호출
3. 되돌리기: 탐색이 끝나면 current에서 마지막 문자를 제거(다른 선택을 위해)

이때 불변식은 항상 current.length() == index 입니다.

---

코드

package algorithm;

import java.util.*;

public class Solution {

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        // 빈 입력 처리
        if (digits == null || digits.isEmpty()) {
            return result;
        }

        // 전화번호 매핑 (인덱스 = 숫자)
        String[] phoneMap = {
                "",
                "",
                "abc",
                "def",
                "ghi",
                "jkl",
                "mno",
                "pqrs",
                "tuv",
                "wxyz"
        };

        backtrack(digits, 0, new StringBuilder(), result, phoneMap);
        return result;
    }

    private void backtrack(String digits, int index, StringBuilder current,
                           List<String> result, String[] phoneMap) {
        // 기저 조건: 모든 숫자를 처리했을 때
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }

        // 현재 숫자에 해당하는 문자들 가져오기
        int digit = digits.charAt(index) - '0';
        System.out.println(digit); // 디버깅용 (제출 전 삭제 권장)
        String letters = phoneMap[digit];

        // 각 문자에 대해 재귀 호출
        for (char letter : letters.toCharArray()) {
            current.append(letter);
            backtrack(digits, index + 1, current, result, phoneMap);
            current.deleteCharAt(current.length() - 1); // 백트래킹
        }
    }

    public static void main(String args[]) {
        String a = "23";
        Solution solution = new Solution();
        System.out.println(solution.letterCombinations(a));
    }
}

라인별 핵심 포인트

• digits == null || digits.isEmpty() → 빈 입력은 빈 리스트(문제 관례)
• phoneMap → 인덱스가 숫자 자체. char - '0' 으로 빠르게 인덱싱
• backtrack
  • index == digits.length() → 결과에 추가하고 종료 (깊이가 완성됨)
  • 현재 자리 숫자의 문자 집합(letters)을 순회하며,
    append → 재귀 → delete(되돌리기)로 모든 경우 탐색

---

시간·공간 복잡도

• 자리 수: n = digits.length()
• 각 자리 최대 문자 수: 4 (7,9의 경우)
• 결과 개수 최대: 4^n
• 시간복잡도: O(n × 4^n) — 결과 문자열 생성/복사까지 고려
• 공간복잡도:
  • 재귀 깊이 O(n)
  • 결과 저장 O(n × 4^n)