← 전체 회차
a-078-letter-combinations-of-a-phone-number2026-08-05mediumleetcode #17neetcode150

전화 번호의 글자 조합

#hash-table#string#backtracking
↗ leetcode #17 · a-078-letter-combinations-of-a-phone-number
01

문제

· problem
P.a-078-letter-combinations-of-a-phone-number

전화 번호의 글자 조합

↗ leetcode #17

2~9 범위의 숫자를 포함하는 문자열이 주어졌을 때, 그 숫자들이 나타낼 수 있는 모든 가능한 글자 조합을 반환하세요. 답은 어떤 순서로든 반환해도 됩니다. 전화 버튼의 숫자-글자 매핑이 다음과 같이 주어집니다. 1은 어떤 글자에도 매핑되지 않습니다.

제약
  • · 1 ≤ digits.length ≤ 4
  • · digits[i] is a digit in the range ['2', '9']
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
"23"
["ad","ae","af","bd","be","bf","cd","ce","cf"]
example 2input → output
"2"
["a","b","c"]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    1은 어떤 글자에도 매핑되지 않나요?
  • ☐
    결과의 순서가 중요한가요?
  • ☐
    빈 문자열이 입력되면 어떻게 되나요?
  • ☐
    가능한 조합의 최대 개수는 몇 개인가요?
  • ☐
    0이나 1이 입력에 포함될 수 있나요?
  • ☐
    같은 숫자가 여러 번 나타날 수 있나요?
  • ☐
    결과를 사전식 정렬(lexicographic order)로 반환해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 결과 리스트 초기화
○
res = []
○
res = {}
○
res = set()
step 2· 숫자→글자 매핑 생성
○
digitToChar = {
○
digitToChar = [["abc"], ["def"], ["ghi"], ["jkl"], ["mno"], ["qprs"], ["tuv"], ["wxyz"]]
○
digitToChar = {"a": "2", "b": "2", "c": "2", ...}
step 3· 백트래킹 재귀함수 정의
○
def backtrack(i, curStr):
○
def backtrack(curStr):
○
def backtrack(i):
step 4· 기저 사례: 모든 숫자 처리 완료│ 중첩
○
if len(curStr) == len(digits):
○
if i == len(digits):
○
if len(curStr) >= len(digits):
step 5· 완성된 조합을 결과에 추가│ │ 중첩
○
res.append(curStr)
○
res.append(list(curStr))
○
res.add(curStr)
step 6· 현재 숫자의 글자들을 순회│ 중첩
○
for c in digitToChar[digits[i]]:
○
for c in digitToChar.values():
○
for c in digits:
step 7· 다음 숫자로 재귀 호출│ │ 중첩
○
backtrack(i + 1, curStr + c)
○
backtrack(i, curStr + c)
○
backtrack(i + 1, c)
step 8· 빈 입력 처리
○
if digits:
○
if len(digits) > 0:
○
if digits != "":
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def letterCombinations(self, digits: str) -> List[str]:
3
        res = []
4
        digitToChar = {
5
            "2": "abc",
6
            "3": "def",
7
            "4": "ghi",
8
            "5": "jkl",
9
            "6": "mno",
10
            "7": "qprs",
11
            "8": "tuv",
12
            "9": "wxyz",
13
        }
14
15
        def backtrack(i, curStr):
16
            if len(curStr) == len(digits):
17
                res.append(curStr)
18
                return
19
            for c in digitToChar[digits[i]]:
20
                backtrack(i + 1, curStr + c)
21
22
        if digits:
23
            backtrack(0, "")
24
25
        return res
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
"23"
→
["ad","ae","af","bd","be","bf","cd","ce","cf"]
case 2
"2"
→
["a","b","c"]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.