LeetCode 17. Letter Combinations of a Phone Number

파이썬 알고리즘 인터뷰 문제 33번(리트코드 17번) Letter Combinations of a Phone Number
https://leetcode.com/problems/letter-combinations-of-a-phone-number/

나의 풀이

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        result = []
        keyboard = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
            }

        def helper(s):
            if len(s) == len(digits):
                result.append(s)
                return
            for char in keyboard[digits[len(s)]]:
                helper(s + char)
        helper("")
        return result

• 여기부터 backtracking 문제들이 나온다.
• 처음으로 backtracking 문제를 풀 때 머리에 쥐가 나는 줄 알았었다. 하루 종일 검색해봐도 어려웠다.
• 그 당시 간단한 재귀(recursive)(피보나치 수열 구하기)는 이해가 되었는데 왜 backtracking은 이해가 안되었던걸까?
• backtracking이 어려웠던 이유는 변수 scope와 call stack에 대한 이해가 부족해서였다.
• 조금 더 자세히 말하자면 부모 함수의 mutable한 변수는 그대로 가져다 쓸 수 있다는 개념을 정확히 몰랐다. path, result 같은 변수를 쓰는게 어색했다.
• 그리고 재귀 함수를 호출하기 전 후에 path에 각각 .append, .pop()하는 과정이 추가되어 이해가 안되었었다.
• 재귀함수가 호출되면 종료되지 않은 채, 계속해서 호출되고 종료는 역순으로 된다는 개념은 이해가 되었으나 .append후 재귀함수가 호출되면 call stack에 대기하다가, 역순으로 차례 차례 종료된 후 다시 .pop()되는 과정을 잘 이해하지 못한 것이다.
• 요약하자면 call stack을 시각화하여 설명한 자료를 검색해서 보고나면 이해가 잘 된다. 본인이 직접 펜으로 노트에 함수에서 호출되는 것을 한 줄씩 stack구조로 그려보는게 제일 좋다.