17. Letter Combinations of a Phone Number

dfs-재귀를 이용한 문제,

 

전화 패드의 숫자를 돌려가면서 출력하는 문제

'2':"abc", '3':"def"가 있고 "23"이면 "ad", "ae", "af"...으로 모두 출력하는 문제

 

끝 조건에서 결과를 append해주면 된다. 

 

맨처음 dfs의 조건을 어떻게 줘야하나 고민했다. 

재귀를 돌리는데, 처음은 뺄수 없어서 0을 줬다.

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        dic = {'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']}
        
        def dfs(index, path):
            if len(path) == len(digits):
                result.append(path)
                return

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

        result = []
        dfs(0, "")
        return result