17. Letter combination of a Phone Number

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

주어진 다이얼(digits)로 조합할 수 있는 문자열들의 조합을 반환하는 문제이다

모든 경우의 수를 전부 고려하는 백트래킹 알고리즘을 이용하여 풀 수 있다.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(idx, path):
        #모든 경우의 수를 탐색한 경우
            if len(digits) == len(path):
                res.append(path)
                return
            for i in range(idx,len(digits)):
            #모든 문자열들을 반복한다
                for j in mapping[digits[i]]:
                    dfs(i+1, path+j)
        if not digits:
            return []
        
        mapping = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', 
                   '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        res = []
        dfs(0,'')
        
        return res

Runtime: 44 ms, faster than 44.42% of Python3 online submissions for Letter Combinations of a Phone Number.
Memory Usage: 14 MB, less than 30.26% of Python3 online submissions for Letter Combinations of a Phone Number.