greentea31's Note

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

풀이 과정

숫자 문자열이 주어졌을때 문자열의 각 숫자로 만들수 있는 알파벳 조합을 리턴하는 문제이다.

'234'가 주어졌다고 가정하면 2에서 a고르고 3으로 넘어가고, b고르고 3으로 넘어가고, c고르고 3으로 넘어가고... 이러한 방법을 반복해주다가 숫자 문자열의 길이와 내가 고른 알파벳 문자열의 길이가 같아지면 정답 배열에 알파벳 문자열을 추가해주면 된다.

일종의 dfs backtracking 문제이다. 숫자 문자열의 길이보다 작은 길이의 알파벳 문자열을 만드는 문제였으면 특정 숫자를 사용할지 사용하지 않을지 고르는 부분도 추가되어야 했을 것이다.

재귀를 사용해 구현하였다.

소스 코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        answer = []
        
        def combi(index, discovered=""):
            if len(discovered) == len(digits):
                if digits:
                    answer.append(discovered)
                return
            for i in dic[digits[index]]:
                combi(index+1, discovered + i)

        combi(0)
        return answer