17. Letter Combinations of a Phone Number

문제링크: https://leetcode.com/problems/letter-combinations-of-a-phone-number/

백준 문제중 n과 m 이라는 문제가 이 문제와 비슷한 구조여서 한번 가지고 와 보았습니다. 이 문제는 백준 문제보다 한단계 쉬운 문제라고 생각하고, 그만큼 여러 풀이가 있을 수 있지만, 그 문제의 prerequisite 이라는 느낌으로 접근해 보겠습니다.

Problem

문제를 보면 숫자열이 먼저 주어집니다. 그 숫자열대로, 핸드폰 자판으로 매핑 할 수 있는 문자열을 모두 출력하면 되는 문제입니다.

간단한 예로, 만약 "23"이 주어졌다면,
["ad", "ae", "af", ..., "cf"]정도가 매핑이 됩니다.

Approach & Solution

처음 생각한 풀이는 완전탐색입니다. 근데 숫자열의 길이가 길어질수록, 반복문을 중첩해서 쌓아야하는데, 그것은 불가능해 보였습니다. 이때, 비슷한 고민을 한 문제가 백준의 n과 m 이어서 백트래킹으로 접근해보았습니다. 하지만 그 문제와 다르게, 탐색을 취소할 경우가 있지 않아 백트래킹이 아닌, DFS 문제라고 결론을 내고 풀어보았습니다.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []
        
        length = len(digits)
        answer = []
        phone = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5":"jkl",
            "6":"mno",
            "7":"pqrs",
            "8":"tuv",
            "9":"wxyz"
        }
        
        def dfs(depth,target):
            if depth == length:
                answer.append(target)
                return
            else:
                alphs = phone[digits[depth]]
                for i in alphs:
                    dfs(depth + 1, target + i)
                    
        dfs(0,"")
        return answer
                

DFS 구조를 잠깐 살펴보겠습니다. DFS함수는 깊이와, 생성될 문자열을 매개변수로 받습니다. 만약, 깊이가 우리가 받은 숫자열과 같은 길이면, 만들어논 문자열을 반환합니다. 만약 아니면, 해당 깊이의 대상이 되는 문자열을 phone안에서 찾아와 DFS 탐색을 반복해 줍니다.

Permutations을 쓰면 더 간단히 풀 수 있을거 같지만, 왠지 문제 의도가 DFS인것 같아 DFS로 풀어보았습니다.