Letter Combinations of a Phone Number | LeetCode 793 | Python3 🐍

 

📄 목차

 

🤔 문제 : Letter Combinations of a Phone Number | LeetCode 793 

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/109/backtracking/793/
숫자 -> 3~4개의 문자 로 매핑될 때

숫자 input이 주어지면 가능한 모든 문자 output을 리스트로 만들어 반환하는 문제입니다. 

 

💡 풀이

1. 접근 -  BFS? DFS?

BFS : 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법

DFS : 하나의 분기를 완벽하게 탐색한 뒤에야 다른 이웃 노드를 방문하는 방법

 

input이 23이라고 할 때 BFS, DFS는 각각 아래의 순서로 결과를 만들어나갑니다.

 

BFS

1. 첫번째 자리에 올 수 있는 문자 탐색 => a b c
2. 두번째 자리에 올 수 있는 문자 탐색 => ad ae af bd be bf cd ce cf

 

DFS

1. a로 시작하는 모든 경우 탐색 => ad ae af
2. b로 시작하는 모든 경우 탐색 => ad ae af bd be bf 
3. c로 시작하는 모든 경우 탐색 => ad ae af bd be bf cd ce cf

 

 

2.  풀이1- recursion을 활용한 DFS

 class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone_pad = {"0" : [" "], "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'] }
        result = []
        digit_length = len(digits)
        if digit_length is 0: return []
    
        def makeString(given_string, index):
            if index is digit_length-1:
                for c in phone_pad[digits[index]]:
                    result.append(given_string+c)
            else:
                for c in phone_pad[digits[index]]:
                    makeString(given_string+c, index+1)
    
        makeString('', 0)
        return result

 

runtime은 63ms로 하위 8%에 속하네요.

recursive하게 call stack을 만들어나가는 연산 자체가 expensive하기 때문인 것 같습니다. 

 

2.  풀이2- DFS

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone_pad = {"0" : [" "], "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'] }
        result = phone_pad[digits[0]] if digits else []
        for d in digits[1:]:
            new_result = []
            for c in phone_pad[d]:
                for str in result:
                    new_result.append(str+c)
            result = new_result
        return result

3중 포문을 활용한 DFS방법입니다. 

탐색 횟수는 동일할 것 같은데 call stack이 없어서인지 속도가 훨씬 빨라졌습니다.