[LeetCode - DiDi Labs 기출 문제] 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

 

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

---

문제 풀이

• 이 문제는 2 부터 9까지의 숫자가 주어지고 그 숫자의 버튼마다 글자를 하나씩 사용해서 단어를 만드는 문제이다.
• 문제 제한을 보면, 글자 조합을 만들때 사용할 수 있는 숫자의 길이가 최악의 경우 4개이다. 
• 즉, 백트레킹을 쉽게 사용할 수 있다.
• 각 숫자들의 문자를 매핑 해준다. 2번부터 9번까지만 만들면된다. 
• 사용하기 쉽게, 0, 1번 인덱스에는 빈 배열을 넣었다.
• 그리고 문자열에 글자를 하나씩 추가하면서 진행하며
• 브랜치(가지)는 숫자 배열에 있는 총 글자 크기만큼 선택한다.
• 깊이는 해당 digits 크기만큼 내려가면서, 해당 숫자 버튼의 알파벳들을 하나씩 선택하여 
• temp 단어에 추가한다. 
• digits 크기만큼 단어가 만들어지면 정답에 넣고 끝낸다. 
• 이를 반복하고 최종 답을 출력한다.

소스 코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        len_dig = len(digits)
        ans = []
        if len_dig == 0:
            return ans
        
        letter_map = [
            [],[],
            ['a', 'b', 'c'],
            ['d', 'e', 'f'],
            ['g', 'h', 'i'],
            ['j', 'k', 'l'],
            ['m', 'n', 'o'],
            ['p', 'q', 'r', 's'],
            ['t', 'u', 'v'],
            ['w', 'x', 'y', 'z']
        ]
        
        def backtracking(idx, digits, temp):
            if idx == len(digits):
                ans.append(temp)
                return
            
            digits_num = int(digits[idx])
            
            for i in range(len(letter_map[digits_num])):
                l = letter_map[digits_num][i]
                backtracking(idx + 1, digits, temp + l)

		backtracking(0, digits, '')
        
        return ans