17. 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.

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: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

풀이

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        alph = [chr(i) for i in range(97,123)] # 소문자 알파벳
        s = 0; e = 0
        nums = {} # 번호판 설정
        for i, j in zip(range(2,10), [3,3,3,3,3,4,3,4]):
            e += j
            nums[str(i)] = ''.join(alph[s:e])
            s += j
            
        res = []
        if not digits: return []
        
        def dfs(x, path):
            if len(path) == len(digits):
                res.append(''.join(path))
                return
            for i in range(x, len(digits)):
                for j in nums[digits[i]]:
                    dfs(i+1, path + [j])
        dfs(0, [])
        
        return res

알고리즘 문제를 풀기 시작하면서 dfs, bfs라는 알고리즘을 접하게 되었고 또 쉽지 않다는 것을 알게되었다. 그래프 관련 문제를 풀게 되면서 이런 dfs, bfs 풀이를 많이 접하게 되었고 처음에는 이해하고 적용하는 것이 굉장히 어려웠지만 점점 익숙해지려고 노력하고 있다.

이번 문제는 키패드의 번호와 문자의 매칭 관계를 고려하여 주어진 숫자의 문자 조합을 구하는 문제이다. 이 때 조합은 단순 조합이 아닌 숫자 순서를 고려하여야 했고 예시를 보면 쉽게 이해할 수 있다.

먼저 키패드의 숫자와 문자 조합을 구성하는 것을 예전에 알게되었던, 아스키코드와 관련된 chr() 를 활용하여 소문자 알파벳을 모두 구해주었고 각 숫자의 문자개수를 입력하여 숫자와 문자 조합을 만들어 주었다. chr()과 ord() 같은 함수는 나중에 알고리즘 문제를 풀 때 분명 유용할 것으로 생각되어 익숙해져야할 것 같다.

키패드가 준비되었다면 이제 input으로 입력되는 숫자의 순서에 따른 문자의 조합을 구해야한다. 단순 조합이 아닌 input 순서에 따라 조합이 이루어지고 input 길이에 따라 조합의 깊이가 달라지기 때문에 dfs 문제라고 판단하였다. 예를 들어, '23'이라는 input이 들어왔을 때, 2에 매칭되는 'abc'와 3에 매칭되는 'def'에서 'ad', 'ae', 'af'가 만들어지고 다음 'be', be', 'bf' 순으로 이루어지기 때문에 깊이를 우선적으로 탐색해야한다고 생각했다.

과정은 간단하다. 말로 표현하기 보다 다음 그림을 보게 되면 굉장히 쉽게 이해할 수 있다.

그림에서 알 수 있듯이, 첫번째 숫자의 첫번째 문자와 이어지는 두번째 숫자의 문자들과 마지막 숫자의 문자들까지의 조합을 먼저 만들고 다음 조합을 만들기 위해 이동하는 것이기 때문에 dfs 알고리즘이라고 볼 수 있다.

이번 문제를 풀게 되면서 dfs 알고리즘을 구현하기 위해 재귀문을 사용하게 되었는데, 확실히 재귀문을 활용하기 위해서는 재귀문이 종료되는 조건과 계속 순환하게 되는 조건에 대해서 확실히 이해하고 들어가야됨을 알게 되었다.