[오답노트] LeetCode #17 Letter Combinations of a Phone Number

교훈
dfs 너무 어려워요... 많이 익혀야 할듯

• LeetCode 문제 링크
• 출처 : 박상길 저, 파이썬 알고리즘 인터뷰, p.338

문제

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.

2-9 사이의 숫자를 포함하는 문자열이 주어지면, 해당 숫자로 만들 수 있는 모든 문자 조합을 반환하라. 순서는 상관 없다.

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

휴대폰 버튼처럼 생긴 아래의 그림에는 숫자 대 글자 대응이 나와 있으며, 1은 아무 문자에도 대응되지 않는다.

Example 1:

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

Example 2:

Input: digits = ""
Output: []

Example 3:

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

Constraints:

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

발상

Solution #1

어차피 digits의 길이는 0, 1, 2, 3, 4 밖에 될 수 없으니까 각 케이스별로 나누면 되잖아?

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        letter = ['', 
                  '', 'abc', 'def', 
                  'ghi', 'jkl', 'mno', 
                  'pqrs', 'tuv', 'wxyz']
        
        result = []
        
        if len(digits) == 1:
            for c1 in letter[int(digits[0])]:
                result.append(c1)
                
        elif len(digits) == 2:
            for c1 in letter[int(digits[0])]:
                for c2 in letter[int(digits[1])]:
                    result.append(''.join([c1, c2]))
                    
        elif len(digits) == 3:
            for c1 in letter[int(digits[0])]:
                for c2 in letter[int(digits[1])]:
                    for c3 in letter[int(digits[2])]:
                        result.append(''.join([c1, c2, c3]))
                        
        elif len(digits) == 4:
            for c1 in letter[int(digits[0])]:
                for c2 in letter[int(digits[1])]:
                    for c3 in letter[int(digits[2])]:
                        for c4 in letter[int(digits[3])]:
                            result.append(''.join([c1, c2, c3, c4]))

		# len(digits) == 0이라면 그냥 빈 리스트 반환
        return result

통과는 한다.

Success
Runtime: 34 ms, faster than 71.70% of Python3 online submissions for Letter Combinations of a Phone Number.
Memory Usage: 13.9 MB, less than 91.67% of Python3 online submissions for Letter Combinations of a Phone Number.

그런데 당연히 추잡하다.

뭔가 일반화가 될 거 같은데, len(digits)에 따라 for문 중첩 개수를 다르게 해야 하니 좀처럼 일반화하기가 어렵다.

이런 건 어떻게 일반화해서 풀 수 있을까?

Solution #2

일반화가 더 어렵게 느껴졌던 이유 중 하나가, 문자열을 합치는 것에 대한 어색함 때문이었다.
'ab'에 'c'를 추가하는 게 너무 어색했다.

그런데 생각해보면, python은 문자열 join을 매우 직관적으로 할 수 있는 방법이 있다.
'ab' + 'c' = 'abc'다!

풀이

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

dfs에 path 정보를 갱신시키면서 함께 전달하는 방식이 매우 신박하다.