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

🔎 문제설명

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.

Example 1

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2

Input: digits = ""
Output: []

Example 3

Input: digits = "2"
Output: ["a","b","c"]

제한사항

• 0 ≤ digits.length ≤ 4
• digits[i] is a digit in the range ['2', '9'].

---

🧊 파이썬 코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits : return []
        tel = ['###', '###','abc', 'def', 'ghi', 'jkl','mno', 'pqrs', 'tuv','wxyz']# 0,1번 인덱스 사용 X
        
        length = len(digits)
        ans = []
        def DFS(i, curS: str):
            if len(curS) == length:
                ans.append(curS)
            for idx in range(i,length):
                for c in tel[int(digits[idx])]:
                    curS += c
                    DFS(idx+1,curS)
                    curS = curS[:-1] #맨뒤 제거
                
        DFS(0,"")
        return ans

단순 DFS문제입니다.