[Leetcode 17] - Letter Combinations of a Phone Number w/ Python

 

 

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의 각 숫자에 알맞은 글자로 만들수 있는 조합을 찾는 문제

 

 

 

 

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

 

 

 

---

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

 

 

 

 

---

 

 

 

 

백트래킹으로 문제를 풀었다

1. 미리 각 숫자가 나타낼수 있는 글자를 HashMap을 통해 만들기

2. 스택에 있는 글자 수가 digits만큼일때 ans에 추가

3. index를 저장해서 각 숫자마다 가능한 조합을 재귀를 통해 확인하기, 다음 숫자로 넘어갈때 마다 index + 1

4. ans return

 

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        numDict = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
                   "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        ans = []
        stack = []

        if digits == "":
            return ans

        def backtrack(index):
            if len(stack) == len(digits):
                ans.append("".join(stack))
                return
            
            for digit in numDict[digits[index]]:
                stack.append(digit)
                backtrack(index + 1)
                stack.pop()
            
            return

        backtrack(0)
        return ans