파이썬 알고리즘 인터뷰 - 33. 전화 번호 문자 조합

 

<--- 리트코드 17. Letter Combinations of a Phone Number --->

# 문제: 2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라.

 

입력

"23"

출력

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

 

 

# 풀이

1. 모든 조합 탐색

def letter_combinations(digits):
  def dfs(index, path):
    if len(path) == len(digits):
      result.append(path)
      return
 
    for i in range(index, len(digits)):
      for j in dic[digits[i]]:
        dfs(i + 1, path + j)
 
  if not digits:
    return
  
  dic = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
 
  result = []
  dfs(0, "")
 
  return result 
 
digits = "23"
print(letter_combinations(digits))