[Leetcode/파이썬] 17. Letter Combinations of a Phone Number

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.

 

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"]

 

Constraints:

• 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 []

        digits_to_letter = {
            '2' : 'abc',
            '3' : 'def',
            '4' : 'ghi',
            '5' : 'jhl',
            '6' : 'mno',
            '7' : 'pqrs',
            '8' : 'tuv',
            '9' : 'wxyz'
        }

        def backtrack(idx, comb) :
            if idx == len(digits) :
                res.append(comb[:])
                return
            
            for letter in digits_to_letter[digits[idx]] :
                backtrack(idx+1, comb + letter)
        res = []
        backtrack(0, '')
        return res

조합을 맞추는 문제로, 옛날에 미국이나 이런 곳에서 전화번호에 영문을 삽입할 때 이와같은 법칙으로 많이 삽입한 것으로 알고 있다. 예를 들면, chicken 의 chic 앞글자만 따서 뒷번호 4자리를 구성할때, chic 를 하여 "2542" 이렇게 구성을 한다던지 이다.

이 문제는 주어진 숫자가 어떤 문자 조합을 만들 수 있는지, 그 조합을 나열하는 문제이다. 조합을 나열하는 문제이기 때문에 백트래킹을 사용하는 문제라고 생각할 수 있다. 

1. 일단 digits_to_letter 를 딕셔너리 형태로 "번호" : "문자" 키-밸류 구조로 완성시켜준다. 
2. 정답을 담을 res 배열을 만들고, 백트래킹 함수를 정의한다.
   1. 백트래킹 함수에는 길이와 문자를 변수로 갖는 함수로 정의한다.
   2. 문자 길이가 현재 주어진 번호의 길이에 도달하면 res 배열에 추가하고, 재귀 스택을 pop 한다.
   3. digits_to_letter에서 digits[idx] 키를 집어넣어서 대응되는 문자를 하나씩 추가한다. 

백트래킹의 정석같은 문제라 다시 한 번 풀어보자.