[LeetCode 17] Letter Combinations of a Phone Number

 

Think

나 왜 이렇게 재귀만 나오면 머리가 멈출까?......

책 풀이만으로는 이해가 안되어서 영상 찾아봤다

https://www.youtube.com/watch?v=0snEunUacZY 

 

 

코드에서 len(path)와 len(digits)의 값이 같을 때 깊이 탐색을 멈추고 백트래킹을 한다는 말이 이해가 안 갔는데

이번에도~ 영상 속 그림을 보고 한방에 이해 됐다

영상 속 그림

digit이 두개니까 지금 탐색중인 path의 길이가 두개이면 끝까지 갔다는 얘기 -> 백트래킹!

지금까지 따라온 경로 = 문자열 하나 인 path를 결과 배열에 저장하고

return 으로 한꺼풀 빠져나온다.

 

 

 

Solution

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        
        #예외 처리 - 아무 숫자도 주어지지 않은 input
        if not digits :
            return []
        
        #숫자에 따른 번호 정의해둠
        dic = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", 
               "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        
        #재귀 함수
        def dfs(index, path) :
            # 지금까지 온 경로 길이 = 입력된 숫자 길이 이면 그래프 끝까지 온 거고 문자열 하나 완성된 것!
            # 문자열 저장 후 백트래킹
            if len(path) == len(digits) :
                result.append(path)
                return
            
            #입력된 숫자개수만큼 반복. 이 때 각 숫자에 대해 오른쪽 방향으로 남아있는 숫자들을 모두 사용하도록 재귀함(내가 써놓고도 이해 안되게 썼다 머리엔 있는데 이걸 뭐라고 하지)
            for i in range(index, len(digits)) :
                for j in dic[digits[i]] : #i번째 숫자에 해당하는 문자들 중 j번째 문자에 대해
                    dfs(i+1, path+j) #i 다음 숫자부터 시작하고, path에 현재 문자j가 추가된 함수를 반복
        
        result = []    
        dfs(0, "")
        return result

 

 

 

Get

재귀 . . .