리트코드 - Letter Combinations of a Phone Number

문제

https://leetcode.com/explore/interview/card/top-interview-questions-medium/109/backtracking/793/

 

문제 설명

주어진 문자열 digits는 2부터 9까지의 숫자로 이루어져 있으며, 숫자는 전화기 버튼에 대응하는 문자로 매핑됩니다.

문자열 digits가 나타낼 수 있는 모든 문자 조합을 반환하세요.  반환되는 순서는 상관없습니다.

 

예시

예제 1

• 입력: digits = "23"
• 출력: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

예제 2

• 입력: digits = ""
• 출력: []

예제 3

• 입력: digits = "2"
• 출력: ["a", "b", "c"]

 

---

 

풀이

해당 문제는 백트래킹(Backtracking) 또는 재귀적 접근으로 해결할 수 있습니다.

1. 기본 매핑 준비:
   • 각 숫자(2~9)에 대한 문자 리스트를 미리 정의합니다.
2. 예외 처리
   • digits가 빈 문자열이면 빈 리스트 []를 반환합니다.
3. 백트래킹(재귀)
   • 현재 숫자의 문자들 중 하나를 선택하여 조합을 생성합니다.
   • 다음 숫자에 대해 반복적으로 같은 작업을 수행합니다.
   • 모든 숫자를 처리하면 완성된 조합을 결과 리스트에 추가합니다.

 

 

---

 

코드

class Solution:
    def combination(self, list_1, list_2):
        
        temp = []
        for a in list_1:
            for b in list_2:
                temp.append(a+b)

        return temp


    def letterCombinations(self, digits: str) -> List[str]:

        dic = {'2' :'abc',
               '3':'def',
               '4':'ghi',
               '5':'jkl',
               '6':'mno',
               '7':'pqrs',
               '8':'tuv',
               '9':'wxyz'
        }

        if digits =='':
            return []
        
        result  = list(dic[digits[0]])

        for digit in digits[1:]:
            result = self.combination(result, list(dic[digit]))

        return result