33. Letter Combinations of a Phone Number

리트코드

• 2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라.

1. 모든 조합 탐색

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        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]]:
                    dfs(i + 1, path + j)
                    
        
        #예외 처리
        
        if not digits:
            return []
        
        dic = {"2": "abc", "3": "def", "4":"ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        
        result = []
        dfs(0, "")
        
        return result
        

• 이 문제는 전체를 탐색하여 풀 수 있다. 항상 전체를 탐색해야 하고 가지치기 등으로 최적화할 수 있는 문제가 아니기 때문에 어떻게 풀이하든 결과는 비슷하다.

• 가능한 경우의 수를 모두 조합하는 형태로 전체를 탐색한 후 백트래킹하면서 결과를 조합할 수 있다.

<"23"의 문자 조합 그래프>

• digits은 입력값이며, 각 자릿수에 해당하는 키판 배열을 DFS로 탐색하면 결과가 완성된다.

• dic는 키판 배열이다. 입력값을 자릿수로 쪼개어 반복하고, 숫자에 해당하는 모든 문자열을 반복하면서 마찬가지로 문자 단위로 재귀 탐색한다.

• dfs( ) 함수는 자릿수가 동일할 때까지 재귀 호출을 반복하다 끝까지 탐색하면 결과를 추가하고 리턴한다.

  • 이렇게 하면 모든 경우의 수를 DFS로 탐색하고 백트래킹으로 결과를 조합하면서 리턴하게 된다.

<백트레킹>

참고

i : 0, j: a, dfs(1, a)
i : 1, j: d, dfs(2, ad)
['ad']
return

i : 1, j: e, dfs(2, ae)
['ad', 'ae']
return

i : 1, j: f, dfs(2, af)
['ad', 'ae', 'af']
return

i : 0, j: b, dfs(1, b)
i : 1, j: d, dfs(2, bd)
['ad', 'ae', 'af', 'bd']
return

i : 1, j: e, dfs(2, be)
['ad', 'ae', 'af', 'bd', 'be']
return

i : 1, j: f, dfs(2, bf)
['ad', 'ae', 'af', 'bd', 'be', 'bf']
return

i : 0, j: c, dfs(1, c)
i : 1, j: d, dfs(2, cd)
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd']
return

i : 1, j: e, dfs(2, ce)
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce']
return

i : 1, j: f, dfs(2, cf)
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
return

i : 1, j: d, dfs(2, d)
i : 1, j: e, dfs(2, e)
i : 1, j: f, dfs(2, f)