Python Algorithm Q33

November 19, 2022

Q33 Letter Combinations of a Phone Number

Q

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Sample Input

Example 1

Input: digits = “23”
Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

Example 2

Input: digits = “2”
Output: [“a”,”b”,”c”]

Example 3

Input: digits = “”
Output: []

Constraints

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].

1. My Own Solution

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

        def dfs(size: int, tmp: str):
            if size <= 1:
                ans.append(tmp)
                return

            for B in numdic[digits[fullsize - size + 1]]:
                dfs(size-1, tmp+B)
            

        
        if(digits):
            for A in numdic[digits[0]]:
                tmp: str = ''
                dfs(fullsize, tmp+A)

        return ans

# test set

a = Solution()

a.letterCombinations("222")

먼저 처음에 numdic을 만들고 시작해야한다는 점은 이견이 없어보인다. 이 dictionary 자체가(즉 숫자와 알파벳의 matching) graph에서 연결된 node들을 표현하는 건가 좀 헷갈렸는데 그냥 반복문 때려넣으라는 것 같고 tree 자체와는 상관 없는 것 같다.

재귀 형식으로 짠 이유는 반복문을 정확히 size만큼만 반복해야하기 때문에 재귀로 size를 1씩 줄여가며 반복하면 풀리겠다는 생각이 들어서이다.

깔끔하게 재귀 안에 모든 for문을 넣을 수 없었던 이유는 size가 1일때 딱 stop하고 return 해야하기 때문이었다. 그래서 line 18을 보면 먼저 for문으로 첫 번째 letter를 firgure out하고 시작함…

이제 dfs 함수를 보면 먼저 몇번 재귀해야할지에 대한 지표로 size를 인수로 받는다. 계속 size를 1씩 줄여나가며 재귀함. 그리고 다음 재귀에 알파벳을 붙여나갈거기 때문에 tmp(string)도 인자로 받는다.

함수에 진입하자마자 먼저 size가 1 or less인지 파악하고 1이면 즉시 list에 append하고 리턴한다.

size가 1이 아니라면, size를 1 깎고 해당 for loop에서 추가된 letter를 붙인 뒤 다음 재귀로 넘긴다. 이때 핵심은 연산한 다음 인자로 넣는게 아니라, 인자로 넣을 때 연산 시킨다. line 13처럼 하라는 소리이다.

# 연산한 다음 인자로 넣는 멍청이 케이스...
for B in numdic[digits[fullsize - size + 1]]:
    size -= 1
    tmp += B
    dfs(size, tmp)

처음에 이렇게 했다가 삽집을 오지게 했다. 여기서 재귀를 반복하는 내내 dfs라는 함수의 area 내부에 있기 때문에 size는 일회성 변수가 아니다. 따라서 한번 값을 까 놓으면 다른 loop에서도 까여있어서 출력을 잘 보면 분명 length가 3인 case에서도 ab 이딴식으로 두자리 return이 나온다. dfs(size-1, tmp)처럼, 함수 내부의 변수에 아무런 영향을 주지 않도록 넣어야한다!!

추가로 line 17을 보면 if digits를 했는데 digit에 아무런 값이 없을 때를 위한 예외 처리이다.

2. Given Solution

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

        def dfs(index, path):
            if len(path) == len(digits):
                result.append(path)
                return

            for i in range(index, len(digits)):
                for j in numdic[digits[i]]:
                    dfs(i+1, path + j)


        if not digits:
            return []

        dfs(0, "")

        return result

numdic 정의하고 시작. dfs에서 처음은 내 풀이와 완전히 동일. 내 풀이는 size를 천천히 낮추는 식으로 했는데 여긴 내가 쌓아가는 letter의 length가 digits의 length와 동일해지면 return하도록 짰다. 이게 좀 더 직관적인듯. 참고로 여기서 index는 내 현재 위치이고 path는 실제로 합쳐지고 있는 문자열이다.

처음 index = 0, path = ‘’ 이므로 line 11을 보면 첫 루프에서 i 는 0 부터 길이-1 까지 대입된다는 것을 알 수 있다. 즉 digits(=input)의 문자열이 맨 앞부터 맨 뒤까지 차례차례 대입된다는 것이다. i = 0 을 대입한 케이스를 살펴보자. 첫번째 자리에 대해서 반복되고(line 12) 여기서 받은 letter와 index(에 1을 추가한 수치)를 다음 재귀로 넘긴다. index가 1이 되었으므로 다시 line 11, 12를 보면 index가 1부터 시작, 즉 digit[i]은 무조건 두 번째 자리값부터 시작한다. index를 계속 쌓아나갈수록 digit의 자리값이 뒤로 점점 이동한다. 따라서 루프가 반복될수록 뒤의 자리값이 오고, path에도 자연스레 뒤의 자리값에 해당하는 문자가 대입된다.

개인적인 평으로는 코드를 되게 이쁘고 체계적으로 잘짜긴 했는데 코드를 읽고 이해하기 전에는 감이 안잡히는…? 느낌이 있다. 내 조잡한 코드보다는 훨씬 좋긴 하다 당연히. 좀 본받고 싶은 점은 당연히 path를 쌓아나가다보면 digit과 같은 자리수가 되는 point가 있고, 그때 return하면 되는데 나는 거꾸로(점점 size가 작아지는 방향)해서 헷갈리는 부분이 많았다.

Overall Review

한 30분간 아 재귀로 짜면 어떻게든 될 것 같긴 한데 어떻게 시작할지 감이 안잡히는 문제였다. 되게 막막하다가 일단 재귀가 끝나는 시점을 정의하고, 시행착오를 천천히 고쳐나가면서 결국에 스스로 풀 수 있었다!! 개뿌듯함 ㅎㅎ

Hyuntae H