[Python][LeetCode] letter Combinations of a phone number(전화번호 문자 조합)

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

문제 설명:

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

이 문제는 전체를 탐색해서 푸는 조합 문제이다.

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

자판기에 다음과 같이 있다고 했을때

'23' 을 입력받으면 'ad' , 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'cd', 'cf' 3*3 = 9개 출력을 하면 된다.

 

풀이

• path = '' 를 정의하고 path 길이와 입력받은 문자열(ex. 23)의 길이가 같아지면 재귀함수를 종료 할 것이다.
• 입력받은 문자열이 없다면 빈 리스트를 반환한다.
• dic['2'] 는 'abc'가 들어있다. 
  • a를 포함한 path와 입력받은 문자열의 다음 인덱스를 넘겨 재귀호출을 해준다.
    • ex) 23을 입력받았다면 1번 인덱스, a 를 넘겨 다시 재귀함수형태로 호출한다.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(index, path):
            if len(digits) == len(path):
                result.append(path)
                return

            for digit in dic[digits[index]]:
                dfs(index+1, path+digit)

        if not digits:
            return []
        dic = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
            "0": "+"
        }
        result = []
        dfs(0, "")
        return result