설명

LeetCode의 Letter Combinations of a Phone Number 문제다.
옛날 핸드폰 버튼에서 많이 볼 수 있는 버튼인데 이 버튼을 눌렀을 때 조합될 수 있는 모든 문자열을 구축하는 문제다.

예를 들어 문제에서 23이 주어진다면 이는 2번 버튼과 3번 버튼을 눌렀다는 것이며 2번 버튼에서 입력할 수 있는 'a', 'b', 'c'와 3번 버튼에서 입력할 수 있는 'd', 'e', 'f'를 조합한 결과를 반환해야 한다. 이때 버튼을 누른 순서는 유지되어야 하며 ["ad","ae","af","bd","be","bf","cd","ce","cf"]가 반환되어야 할 것이다.

풀이

DFS(32 ms)

언급했듯이 문자열로 주어진 버튼의 순서는 지켜져야 한다. 그렇기 때문에 BFS보다는 DFS를 이용하여 해결할 수 있는데 예를 들어 다음처럼 트리를 구축한다면 먼저 누르는 버튼과 다음에 누르는 버튼을 잇도록 구축할 수 있다.
당연히 BFS로 탐색하면 제대로 문자열이 구축되지 않기 때문에 DFS로 탐색하는 방법으로 구현할 수 있다.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # DFS 탐색을 위한 내부 함수 정의.
        def findCombination(level, combination):
            # 탐색 종료 조건.
            if level >= len(digits):
                combinations.append(combination)
                return
            
            # 다음 버튼의 문자와 조합하여 탐색.
            for character in buttons[digits[level]]:
                findCombination(level+1, combination+character)
                
        # 예외처리.
        if not digits:
            return []
        
        # 탐색을 위한 버튼 문자 생성.
        buttons = {
            "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']
        }
        
        # DFS 탐색.
        combinations = []
        findCombination(0, "")
            
        return combinations

각 버튼의 문자를 사전으로 구축해두기만 하면 어렵지 않게 풀 수 있는 문제였다.

반복(32 ms)

재귀 호출을 이용한 DFS 대신 단순히 반복문으로 앞뒤 버튼의 문자를 조합시켜서 등록하는 방법을 사용할 수도 있다.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 기본적인 예외처리.
        if not digits:
            return []
        
        # 각 버튼의 문자를 담은 사전.
        buttons = {
            "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']
        }
        
        # 조합된 문자열들이 담긴 리스트.
        combinations = []
        # 첫 번째로 누른 버튼의 문자를 등록.
        combinations.extend(buttons[digits[0]])
        
        # 두 번째 버튼부터 문자 조합.
        for digit in digits[1:]:
            # 현재 버튼의 문자로 조합된 문자열을 담을 새로운 리스트.
            newCombination = []
            # 이전 버튼까지 조합된 문자열: combination
            # 현재 버튼의 문자: numpad
            # 문자열과 문자를 조합하여 새로운 리스트를 구축.
            for combination in combinations:
                for numpad in buttons[digit]:
                    newCombination.append(combination+numpad)
            
            # 새로 구축된 리스트로 변경.
            combinations = newCombination
            
        return combinations

DFS 풀이와 코드는 다르지만 기본적인 방법은 동일하다. 이전 버튼까지 조합된 문자열에 현재 버튼의 문자들을 붙여서 새로운 문자열을 생성하면 된다.