leetCode - Letter Combinations of a Phone Number

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

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        
        # exception case 1: no input
        if not digits:
            return []
        
        
        # mapping
        map = {
            '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'}
        }
        
        
        # exception case 2: one input
        if len(digits) == 1:
            return list(map[digits[0]])
        
        
        # pseudo code
        """
        DFS over tree
        combinations = []
        combination = ""
        def DFS(node):
            if last:
                combinations.append(combination)
                return
            when backtracking:
                remove last character from combination
            combination += node
            for every next node:
                DFS(next node)
        DFS(digits[0])
        return combinations
        """
        
        
        combinations = []
        
        def DFS(idx, node, combination):
            combination += node
            if idx == len(digits) - 1:
                combinations.append(combination)
                return
            for next_node in map[digits[idx + 1]]:
                DFS(idx + 1, next_node, combination)
            combination = combination[:-1]
            
        for node in map[digits[0]]:
            DFS(0, node, "")
            
        return combinations

 

첫 번째 숫자의 문자들이 각각 트리의 루트인 그림을 떠올리고 이를 DFS로 탐색하면서 빈 문자열로 초기화한 combination에 대해

1. 노드를 내려갈 때마다 combination에 그 노드의 문자 추가

2. 백트래킹 할 때마다 combination의 마지막 문자 제거

3. 리프에 도달하면 combinations에 여태 쌓은 combination을 append

이렇게 하여 모든 combination들을 combination에 넣었다.