33. Letter Combinations of a Phone Number

🎯 leetcode - 17. Letter Combinations of a Phone Number

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 33번 문제
- 숫자가 주어졌을때 전화번호의 문자들로 조합 가능한 모든 문자를 출력하라.

📌 날짜

2020.02.04

📌 시도 횟수

2 try

💡 Code

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        digit2letters = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        if not digits:
            return None

        letters = list([" ", " ", " ", " "])  # 아래 for문 돌아가도록 일단 " " 으로 초기 설정
        for i in range(4):
            if i < len(digits):  # digit의 개수만큼 letters[i]을 초기화
                letters[i] = digit2letters[digits[i]]

        result = []
        for f in letters[0]:
            for s in letters[1]:
                for t in letters[2]:
                    for fr in letters[3]:
                        result.append(str(f + s + t + fr).rstrip())
                        # digit이 4개보다 적더라도 4중 for문 돌아가도록 공백 넣고 나중에 오른쪽 공백 제거

        return result

💡 문제 해결 방법

- 문제 조건 중에...
→ Constraints: 0 <= digits.length <= 4 
라고 되어 있길래 혹시..? 하고 브루트 포스로 풀어봤는데 통과 했다ㅎ...

1. 일단 최대 digits는 4개라고 하니 해당 digits의 알파벳을 담을 letter list를 준비한다.
2. letter 리스트는 " "으로 초기화한다. (""가 아닌 이유는 이후에 나오는 4중😅 for문 돌리려고..)
3. 4중 for문을 돌면서 letters[0] ~ letters[3]의 각 문자가 합쳐진 조합을 구한다.
4. 구한 조합을 result에 더하기 전에, 만약 해당 문자열의 오른쪽에 공백이 있다면 rstrip으로 제거한다.
(digits.length가 4인 경우에는 공백이 없지만, 그보다 작은 경우에는 공백이 생기므로 제거해주어야 한다.)
5. 모든 조합을 구하고 result를 리턴한다.

💡 새롭게 알게 된 점

- 솔직히 브루트포스로 풀면 시간초과 뜰 줄 알았는데 통과됐다
- 그래도 이 방법은 문제의 의도에 맞지 않다~~ dfs로 푸는 방법을 제대로 익히자.

😉 다른 풀이

📌 하나. DFS로 모든 조합 탐색

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(index, path):
            # 끝까지 탐색하면 백트래킹함
            if len(path) == len(digits): # 조합된 알파벳 개수 == digits의 길이
                result.append(path)
                return

            for i in range(index, len(digits)):
                for j in dic[digits[i]]:
                    dfs(i + 1, path + j) # 해당 digits[i]에 대한 모든 조합 탐색

        dic = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
	# 간단한 예외 처리
        if not digits:
            return None

        result = [] 
        dfs(0, "") # 처음부터 모든 조합 탐색

        return result

💡 문제 풀이 방법

- len(path) 자릿수가 동일해질때까지 DFS 재귀 호출을 반복
- 자릿수가 같아지는 시점에는 탐색을 중지하고 리턴
- 모든 경우의 수를 DFS로 탐색하고 백트래킹으로 결과를 조합하면서 리턴 하게 됨

💡 새롭게 알게 된 점

- 모든 조합 케이스를 DFS 재귀와 백트래킹으로 구하는 방법을 알게 되었다.