[파이썬 알고리즘] 12장 - 전화번호 문자 조합

 

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

Letter Combinations of a Phone Number - LeetCode

 

<문제>

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

 

 

<예시>

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Input: digits = ""
Output: []

Input: digits = "2"
Output: ["a","b","c"]

---

1. 나의 풀이

# my solution
# faster than 94% (24ms)
# less than 20% (14.4MB)
class Solution:
    def iterate(self, digits: List, result: List, i):
        num_to_alpha = {
            '2': ["a", "b", "c"],
            '3': ["d", "e", "f"],
            '4': ["g", "h", "i"],
            '5': ["j", "k", "l"],
            '6': ["m", "n", "o"],
            '7': ["p", "q", "r", "s"],
            '8': ["t", "u", "v"],
            '9': ["w", "x", "y", "z"]
        }

        if i == len(digits):
            return result
        elif i == 0:
            return self.iterate(digits, num_to_alpha[digits[i]], i+1)
        else:
            alphas = num_to_alpha[digits[i]]
            length = len(result)
            for _ in range(length):
                tmp = result.pop()
                for alpha in alphas:
                    result.insert(0, tmp + alpha)
            return self.iterate(digits, result, i+1)

    def letterCombinations(self, digits: str) -> List[str]:
        if str == "":
            return []
        else:
            digits = list(digits)
            result = []
            return self.iterate(digits, result, 0)

 

digits = "23"이라면

먼저 숫자 2에 대응되는 문자들의 리스트인 ["a", "b", "c"]가 result가 된다.

 

이후 result에서 pop해서 "c"를 뽑아낸 뒤, 3에 대응되는 문자들 ("d", "e", "f")과 결합한 뒤 리스트에 넣는다.

따라서 new_result에는 ["cd", "ce", "cf", "a", "b"]가 들어있다.

 

다시 pop해서 "b"를 뽑아낸 뒤, 마찬가지로 3에 대응되는 문자들 ("d", "e", "f")과 결합한 뒤 리스트에 넣는다.

따라서 new_result에는 ["bd", 'be", "bf", "cd", "ce", "cf", "a"]가 들어있다.

 

이후 다시 pop해서 "a"를 뽑아내고 위와 같은 과정을 거친다.

 

 

재귀의 종료조건은 

if i == len(digits):
    return result

을 이용하여 만들어주었다.

 

---

2. 책의 풀이

# faster than 55% (32ms)
# less than 20% (14.3MB)
class Solution2:
    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