Leetcode 17. Letter Combinations of a Phone Number - Python

from LeetCode17

Leetcode 17 문제 보기

 

문제 이해하기

스마트폰이 출현하기 이전, 휴대폰의 자판은 위 그림과 같았다.

전화번호의 각 번호는 특정 알파벳들과 매칭이 된다.

어떤 번호가 주어진다면, 해당 번호를 이용해 출력 가능한 단어들을 구하라.

번호는 2~9로 이루어져 있으며, 번호의 길이는 최소 0부터 최대 4까지 가능하다.

 

아이디어 구상

Decision Tree를 그리며 생각해보자.

digits = "23"인 test case를 살펴보자.

By Mesotes

 

이 때 트리의 각 level은 주어진 digits의 각 숫자를 탐색하는 경우에 해당된다.

모든 조합을 찾아야하므로, Brute Force하게 탐색을 해야한다.

DFS를 활용해 가능한 알파벳 조합들을 하나씩 얻어 결과 리스트에 넣고, 최종적으로 정답을 출력하면 되겠다.

 

이 때의 시간복잡도는 어떻게 될까?

각 숫자들은 3개 혹은 4개의 알파벳과 매칭된다.

따라서 최악의 경우, n = len(digits)라 했을 때 출력가능한 조합의 갯수는 4 ^ n개,

여기에 각 조합의 길이 또한 n이므로, 전체 시간복잡도는 대략 O(n * (4^n))이 될 것이다.

즉, Time Complexity ~ O(n * (4^n)) 가 예상된다.

 

물론 대부분의 숫자가 3개의 알파벳과 매칭된다는 점을 고려하면, 실제 시간복잡도는 이보다는 나을 것으로 생각된다.

 

풀이

문제 풀이를 위해 필요한 도구(변수, 함수 등)들을 생각해보자.

결과를 담을 res 리스트, 숫자와 알파벳들을 매칭시켜줄 map, dfs 함수가 필요할 것이다.

res = []
digit_to_char = {
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "qprs",
    "8": "tuv",
    "9": "wxyz"
}
def dfs()

 

dfs()를 구현해보자.

 

우선 base case는 다음과 같다.

digits를 탐색할 때 사용하는 index가 len(digits)와 같아질 때 leaf node에 도달할 것이며, 이 때의 알파벳 조합을 res에 담는다.

if i == len(digits):
    res.append(path)
    return

 

재귀 부분은 다음과 같다.

digitis의 특정 숫자와 매칭되는 알파벳들에 대하여 순차적으로 dfs()를 다시 호출하여 조합을 구성한다.

for ch in digit_to_char[digits[i]]:
    dfs(i + 1, path + ch)

 

전체 코드는 다음과 같다.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        digit_to_char = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "qprs",
            "8": "tuv",
            "9": "wxyz"
        }
        
        
        def dfs(i, path):
            # base case
            if i == len(digits):
                res.append(path)
                return
            
            for ch in digit_to_char[digits[i]]:
                dfs(i + 1, path + ch)
        
        # if digits = "": output = []
        if digits:
            dfs(0, "")
            
        return res

 

---

Leetcode 17. Letter Combinations of a Phone Number

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

 

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다