[LeetCode] 17. Letter Combinations of a Phone Number - Python

[LeetCode] 17. Letter Combinations of a Phone Number - Python

 

Letter Combinations of a Phone Number - LeetCode

 

문제

2부터 9까지의 숫자를 포함한 digits문자열이 주어졌을 때, 전화번호로 조합 가능한 모든 문자를 출력하세요.

숫자별로 가질 수 있는 문자들은 아래 이미지와 같습니다.

 

 

아이디어

먼저 각 숫자를 키로, 숫자에 해당하는 문자열을 값으로 하는 딕셔너리를 생성한다.

digits에 해당하는 숫자들을 차례대로 하나씩 선택하고, 점점 아래로 들어가서 가장 아래 깊이까지 도달하면 그때부터 경우의 수를 저장하는 방식으로 문제를 해결했다.

재귀함수를 통해 아래 깊이까지 점차 내려갈 수 있다.

 

예를 들어 digits = '23'이라면 2에 해당하는 문자열 중 첫번째인 'a'를 선택하고, 아래 깊이로 내려가서 먼저 'd'를 선택한다. 이때 깊이가 최대가 되므로 'ad'를 저장하고, 같은 깊이에서 그 다음 문자열인 'e'를 선택하는 방식이다.

 

 

코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
    
    	#초기 설정
    	dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        result = []
    
        def dfs(index, path):  #index: 깊이 
        
            #가장 아래 깊이까지 도달, 저장할 경우의 수
            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)  #i+1을 통해 아래로 들어감, path+j로 각 깊이에서 경우의 수 하나씩 할당

        #예외 처리
        if not digits:
            return []


        dfs(0, '')

        return result