[리트코드(LeetCode)] 17번 Letter Combinations of a Phone Number

문제

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Letter Combinations of a Phone Number - LeetCode

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

예시

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

 

Example 2:

Input: digits = ""
Output: []

 

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

풀이

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        digit_dict = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
	# 현재 숫자의 인덱스(idx)와 지금까지 만들어진 문자 조합(path)을 매개변수로 받는다.
        def dfs(idx, path):
        # 길이가 같다면 모든 숫자에 대한 문자가 선택된 것으로 결과리스트에 현재까지 문자 조합을 추가
            if len(path) == len(digits):
                res.append(path)
                return
	# 현재 숫자에 대한 가능한 문자들을 순회하면서 다음 숫자로 넘어가며 재귀적으로 호출
            for i in range(idx, len(digits)):
                for j in digit_dict[digits[i]]:
                    dfs(i + 1, path + j)
            
        res = []
        
        dfs(0, '')

        return res

 

- 깊이 우선 탐색(DFS)을 사용하여 가능한 문자 조합을 찾고, 그 결과를 반환한다.

- dfs 함수는 현재 숫자의 인덱스(idx)와 지금까지 만들어진 문자 조합(path)을 매개변수로 받는다.

- path의 길이가 digits의 길이와 같을 때까지 현재 숫자에 대한 가능한 문자들을 순회하면서 다음 숫자로 넘어가며 재귀적으로 호출한다. 길이가 같다면 모든 숫자에 대한 문자가 선택된 것으로 결과리스트에 현재까지 문자 조합을 추가한다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview