[LeetCode 해석 및 풀이] 17. Letter Combinations of a Phone Number(전화번호의 문자 조합)

LeetCode 문제 해석 및 풀이 방법

문제 17. 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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

 

한글

2-9 까지의 숫자를 포함하는 문자열이 주어지면 숫자가 나타낼 수 있는 모든 가능한 문자 조합 을 반환합니다. 어떤 순서 로든 답을 반환합니다.

 

숫자에서 문자로의 매핑(전화기 버튼과 마찬가지로)은 사진과 같습니다. 1은 어떤 문자에도 매핑되지 않는다는 점에 유의하세요.

 

제한조건

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

 

입출력 예

입력	출력
digits = "23"	["ad","ae","af","bd","be","bf","cd","ce","cf"]
digits = ""	[]
digits = "2"	["a","b","c"]

 

해답 및 해설

파이썬 (Python)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []
 
        elif len(digits) == 1:
            num = int(digits)
            return ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'][num-2]
 
        last_output = self.letterCombinations(digits[:-1])
        new_char = self.letterCombinations(digits[-1])
        output = []
 
        for last in last_output:
            for char in new_char:
                output.append(last+char)
        
        return output

내가 처음에 푼 풀이

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        digitToChar = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "qprs",
            "8": "tuv",
            "9": "wxyz",
        }
 
        def backtrack(i, curStr):
            if len(curStr) == len(digits):
                res.append(curStr)
                return
            for c in digitToChar[digits[i]]:
                backtrack(i + 1, curStr + c)
 
        if digits:
            backtrack(0, "")
 
        return res

neetcode 로드맵에서의 풀이도 신기해서 가져와봤다.