[leetcode 2024/02/15] 17. Letter Combinations of a Phone Number

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

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

이번 문제는 DFS 를 이용하는 문제라고 파악하였다. 

왜냐하면, 각각의 letter 마다 이어지는 여러가지의 수가 있기 때문이다.

 

우선 숫자에 따라 연결된 alphabet들을 dictionary로 정리해주었다.

num_dict = { '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']}

 

이제 dfs를 구성해줄 차례이다.

 

1. 탈출 조건:

len(digits) 가 dfs를 반복한 횟수와 같을 때로 정했다.

 

2. dfs ( dfs 반복 횟수, 연결되어지는 문자열) 로 구성했다.

 

처음부터 순서를 시각화해서 나타내보도록 하겠다.

 

digits = "23" 인 것을 예로 들어볼 것이다.

 

digits[0] -> '2'

digits[1] -> '3' 일 것이다.

 

for char in num_dict[digits[0]] 에서 char은 순서대로 'a', 'b', 'c' 를 내뱉을 것이다.

이때 path = "" 라는 문자열을 넣는 곳에, path + char를 통해 각각 문자를 넣어준다.

이를 다시 dfs로 반환하여, digits[1] 조건에서도 실행하도록 한다.

 

이런식으로 구성되게 된다.

 

2. 코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        
        num_dict = { '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 index == len(digits):
                res.append(path)
                return

            for char in num_dict[digits[index]]:
                dfs(index + 1, path + char)

        res = []
        dfs(0, "")

        return res