[LeetCode] 17 | Letter Combinations of a Phone Number | Python

---

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

---

문제

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 digit 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'].

---

내 풀이

각 숫자에 해당되는 문자를 정리해놓는다(self.d2l).

digits의 길이는 최대 4이므로 recursion으로 푼다.

---

코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == '':
            return []
        
        self.d2l = {'2': 'abc',
                    '3': 'def',
                    '4': 'ghi',
                    '5': 'jkl',
                    '6': 'mno',
                    '7': 'pqrs',
                    '8': 'tuv',
                    '9': 'wxyz'}
        self.digits = digits
        self.ans = []
        
        self.comb(0, '')
        return self.ans
        
    
    def comb(self, idx, lcomb):
        if idx == len(self.digits):
            self.ans.append(lcomb)
            return
        
        for letter in self.d2l[self.digits[idx]]:
            self.comb(idx+1, lcomb+letter)