[LeetCode] 17. Letter Combinations of a Phone Number - 파이썬(Python)

문제 링크 : https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Letter Combinations of a Phone Number - LeetCode

유형 : 백트래킹(BackTracking)

문제 설명

숫자를 포함하는 문자열인 digits이 입력으로 주어졌을 때, Phone Keypad를 통해 해당 digits으로 만들 수 있는 모든 문자 조합을 return하는 문제이다. return되는 문자 조합의 순서는 상관없다. 숫자에 따라 문자를 매핑할 수 있는 Phone Keypad는 아래 그림과 같다.

제한사항

• 0 <= digits.length <= 4
• digits[i]는 2~9 사이의 숫자이다.

문제 풀이

주어진 digits으로 만들 수 있는 모든 문자 조합을 찾으면 되는 문제이기 때문에 백트래킹을 통해 문제를 해결할 수 있다.

 

그럼 코드를 작성하기 앞서 간단히 재귀의 구조를 아래 그림을 통해 살펴보자.

만약 digits이 "259"라면 위 그림처럼 Decision Space를 가지게 된다. 그리고 digits의 인덱스를 하나씩 읽어가면 재귀적으로 백트래킹을 진행하면 되고 재귀의 index가 digits.length인 3이 되었을 때, 재귀를 종료하면 된다.

 

또한 숫자와 문자가 매칭되는 Phone Keypad를 그림의 오른쪽 해시맵처럼 구현할 수 있는데 key 값들이 1부터 연속되는 양의 정수 값들이기 때문에 단순히 배열로 나타낼 수 있다.

 

이제 코드를 작성해보자. 먼저 작성할 코드의 구조를 그림으로 나타내면 아래와 같다.

성공 코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        self.keypad = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
    
        if len(digits) == 0:
            return []
    
        self.digits = digits
        self.comb = []
        self.bt(0, '')
        
        return self.comb
    
    def bt(self, index: int, crntStr: str):
        if index == len(self.digits):
            self.comb.append(crntStr)
            return
        
        num = int(self.digits[index])
        chars = self.keypad[num]
        for char in chars:
            self.bt(index+1, crntStr+char)

시간복잡도 : O(n*4^n)

공간복잡도 : O(n)