[코테] 리트코드 그래프 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

문제 링크

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

문제 설명

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

제한 사항

• 0 <= digits.length <= 4
• digits[i] is a digit in the range [‘2’, ‘9’].

입출력 예 #1

1. Input : digits = “23”
2. Output : [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

입출력 예 #2

1. Input : digits = “”
2. Output : []

입출력 예 #3

1. Input : digits = “2”
2. Output : [“a”,”b”,”c”]

문제 풀이

dfs 기법을 이용하여 입력 가능한 문자열 모두를 출력한다.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(index, path):
            # 끝까지 탐색하면 백트래킹
            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)
                
        # 예외 처리
        if not digits:
            return []

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