출처 : 파이썬 알고리즘 인터뷰

분명 어젯밤에 1일차 한 것 같은데 일어나자마자 2일차 시작..

오늘 풀어볼 문제는 leetcode 17 Letter Combinations of a Phone Number 입니다요.

예시 입출력만 봐도 느낌이 오는...조합 문제라고 할 수 있겠다.

"23"을 입력받으면 그 번호키에 맞는 문자들을 조합해서 나오는 경우들을 배열로 반환하는 문제.

생각의 흐름

모든 경우의 수를 구하는 문제군
-> 2의 abc, 3의 def를 조합해야되는 문제군
-> a 다음에 d, e, f 순으로 탐색하면 되겠군.
-> 그래프로 생각하자

탐색 종료 조건?
-> digits의 길이와 구한 문자열의 길이가 같을 때 result에 추가하고 return
( + 입력값이 잘못된 경우)

1. 그래프로 생각해보기

딕셔너리로 저장할 생각

dic = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}

dfs인수로 무엇을 받을까

=> 탐색할 숫자의 index & 현재까지 만든 문자열(path)

탐색 시작 (2중 for문)

for i in range(index, len(digits)):
	for j in dic[digits[i]):
    	dfs(index+i, path+j)

2. 어떻게 탈출?

digits의 길이 == path의 길이일 때 탈출한다.

if len(digits) == len(path):
	result.append(path)
    return

최종코드

    def letterCombinations(self, digits: str) -> List[str]:
        dictionary = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
        result = []
        
        if not digits: return[]
        
        def dfs(index, path):
        	if len(path) == len(digits):
            	result.append(path)
                return
                
            for i in range(index, len(digits)):
            	for j in dicionary[digits[i]]:
                	dfs(index+i, path+j)
                    
        
        dfs(0, "")
        
        return result