[리트코드] Letter Combinations of a Phone Number(python)

리트코드, Letter Combinations of a Phone Number_핸드폰 글자 조합하기

TL;DR

• DFS

문제 분석

1. 핸드폰 자판 2-9에는 문자들이 할당되어 있다.
2. 주어진 자판 조합에 대해서 만들 수 있는 모든 문자들을 반환하라.
3. 반환하는 문자의 순서는 상관 없다.

 

- 문제에서 주어진 핸드폰 2 ~ 9에는 a ~ z까지의 문자가 할당되어 있다.

- 문제에서 숫자 조합을 주어지면 해당 문자에 할당된 알파벳을 조합할 수 있는 모든 경우의 수를 반환하면 된다.

입출력 형태

입출력 예시

 

- 예시 1 : 자판 23이 주어졌다면 만들 수 있는 조합은 "abc"와 "def"를 활용한 총 9개의 조합이다.

- 예시 3 : 하나의 자판이 주어졌다면 만들 수 있는 조합은 할당된 알파벳은 "abc"를 각각 한 번 사용한 3개의 조합을 만들 수 있다.

풀이

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result = []
        
        if digits == '':
            return result
        
        dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
               '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        
        # recursive
        def dfs(word: str, index: int = 0):
            if len(word) == len(digits):
                result.append(word)
                return
            
            for i in range(index, len(digits)):
                for j in dic[digits[i]]:
                    dfs(word + j, i + 1)
        
        dfs('')
        return result

 

- 재귀적인 방법을 사용하여 DFS를 구현한 코드이다. 우선, 각 숫자에 할당된 문자들을 딕셔너리로 선언해준다.

- dfs 함수는 두 가지 인자를 받는다. 하나는 만들 수 있는 단어 word이고, 또 다른 하나는 주어진 자판 조합의 인덱스를 나타내는 inde이다.

- 우선, 종료 조건을 살펴보면 조합된 단어의 길이가 자판의 길이와 같을 때 해당 문자를 결과 배열이 삽입하고 종료한다. 자판이 두 개가 입력된다면 만들어진 문자의 길이 또한 2여야 하기 때문이다.

- index부터 입력으로 주어진 문자열의 길이까지 반복문을 수행한다. 이 반복문에서 각 자판의 숫자에 할당된 문자를 조회하게 된다.

- 두 번째 반복문에서는 자판에 해당하는 문자열들을 반복한다. 이 때, 조회한 문자열과 다음 인덱스를 dfs의 인자로 넘겨 재귀적으로 수행한다.

다른 풀이

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result = []
        
        if digits == '':
            return result
        
        dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
               '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        
        stack = [('', 0)]
        while stack:
            word, index = stack.pop()
            
            for i in range(index, len(digits)):
                for j in dic[digits[i]]:
                    stack.append((word + j, i + 1))
                    
            if len(word) == len(digits):
                result.append(word)
                    
        return result

 

- 스택을 활용하여 DFS를 구현한 코드이다.

- 재귀적인 방법과 마찬가지로 스택은 비어있는 문자와 초기 인덱스 값을 갖고 있다.

- 만들어진 단어의 길이가 입력으로 주어진 자판의 길이와 같다면, 결과 배열에 삽입한다.

- 자판과 자판에 해당하는 글자들을 조회하며 스택에 입력과 출력이 반복되고, 최종적으로는 자판에 해당하는 글자들로 조합한 문자를 얻어낼 수 있다.