🔍17. Letter Combinations of a Phone Number - [해시테이블, 문자열, 백트래킹]

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

 

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

---

 

Q.
특정한 숫자가 주어졌을 때,
각각의 숫자버튼으로 표현할 수 있는 모든 알파벳의 조합을 반환해라. 

이때 1은 어떤 문자도 매핑할 수 없다.

---

def letterCombinations(self, digits: str) -> List[str]:
    def dfs(index, path):
        # 끝까지 탐색하면 백트래킹
        if len(path) == len(digits):
            result.append(path)
            return


        # 입력값 자릿수 단위 반복
        for i in range(index, len(digits)):
            # 숫자에 해당하는 모든 문자열 반복
            for j in dic[digits[i]]:
                dfs(i + 1, path + j)

    # 예외 처리
    if not digits:
        return []

    dic = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
           "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
    result = []
    dfs(0, "")


    return result

 

 

---

참고

- 파이썬 알고리즘 인터뷰, 340쪽