LeetCode - 17. Letter Combinations of a Phone Number (Python)

Medium, 백트래킹

RunTime : 42 ms / Memory : 16.71 MB

문제

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.

풀이

• 처음엔 combinations를 통해 풀까 했는데, 백트래킹으로 해결하는 방법을 참고했다.
• 조금 생각을 해야되는 문제, S1 정도는 되지 않을까

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []
        
        cvt = {
            '2' : ['a', 'b', 'c'],
            '3' : ['d', 'e', 'f'],
            '4' : ['g', 'h', 'i'],
            '5' : ['j', 'k', 'l'],
            '6' : ['m', 'n', 'o'],
            '7' : ['p', 'q', 'r', 's'],
            '8' : ['t', 'u', 'v'],
            '9' : ['w', 'x', 'y', 'z']
        }

        res = []

        def dfs(comb, nxt):
            if not nxt:
                res.append(comb)
                return
            
            for w in cvt[nxt[0]]:
                dfs(comb + w, nxt[1:])
        
        dfs("", digits)
        return res