Leetcode Python - 17. Letter Combinations of a Phone Number

Leetcode #17 - Letter Combinations of a Phone Number

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. string을 집중적으로 풀어보겠습니다.

리트코드의 문제 17 ‘Letter Combinations of a Phone Number’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 dfs를 이용해 recursion하게 풀 수 있습니다.

전체 코드는 아래와 같습니다.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        res = []
        self.recursion(digits, '', res)
        return res
    
    def recursion(self, digits, path, res):
        if not digits:
            res.append(path)
            return
        
        if digits[0] == '2':
            for ch in ['a','b','c']:
                self.recursion(digits[1:], path + ch, res)
        elif digits[0] == '3':
            for ch in ['d','e','f']:
                self.recursion(digits[1:], path + ch, res)
        elif digits[0] == '4':
            for ch in ['g','h','i']:
                self.recursion(digits[1:], path + ch, res)
        elif digits[0] == '5':
            for ch in ['j','k','l']:
                self.recursion(digits[1:], path + ch, res)
        elif digits[0] == '6':
            for ch in ['m','n','o']:
                self.recursion(digits[1:], path + ch, res)
        elif digits[0] == '7':
            for ch in ['p','q','r','s']:
                self.recursion(digits[1:], path + ch, res)
        elif digits[0] == '8':
            for ch in ['t','u','v']:
                self.recursion(digits[1:], path + ch, res)
        elif digits[0] == '9':
            for ch in ['w','x','y','z']:
                self.recursion(digits[1:], path + ch, res)

시간복잡도는

• 평균 O(3^logn) : 한번에 3개 or 4개씩 더 곱해나가므로

공간복잡도는

• 최악의 경우 O(3^logn) : 수행되는 모든 함수만큼 res에 더해짐