[파이썬(python)] 리트코드 17 Backtracking

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=top-interview-150

 

Backtracking 문제라는데 한번도 백트래킹을 풀어본적이 없다.

그래서 다음과 같이 d의 개수에 따라 반복문을 생성하는 아주 비효율적인 코드를 생각해냈는데

통과가 되긴 했다.

 

시간복잡도 : digits의 길이가 n이라면, O(3^n)

공간복잡도 : O(n*3^n)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        
        telephone = {'2':['a','b','c'], '3':['d','e','f'], '4':['g','h','i'], '5':['j','k','l'], '6':['m','n','o'], '7':['p','q','r','s'], '8':['t','u','v'], '9':['w','x','y','z']}
        output = []

        d = len(digits)

        if d == 0:
            return output
        elif d == 1:
            for i in telephone[digits[0]]:
                output.append(i)
            return output
        elif d == 2:
            for i in telephone[digits[0]]:
                for j in telephone[digits[1]]:
                    output.append(i+j)
            return output
        elif d == 3:
            for i in telephone[digits[0]]:
                for j in telephone[digits[1]]:
                    for k in telephone[digits[2]]:
                        output.append(i+j+k)
            return output
        elif d == 4:
            for i in telephone[digits[0]]:
                for j in telephone[digits[1]]:
                    for k in telephone[digits[2]]:
                        for l in telephone[digits[3]]:
                            output.append(i+j+k+l)
            return output

 

그런데 이 문제를 재귀로 푼다면? 그게 backtracking이었다.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        telephone = {'2':['a','b','c'], '3':['d','e','f'], '4':['g','h','i'], '5':['j','k','l'], '6':['m','n','o'], '7':['p','q','r','s'], '8':['t','u','v'], '9':['w','x','y','z']}

         def backtrack(index, current_combination):
            # 기저 조건: 모든 자리를 다 처리한 경우
            if index == len(digits):
                result.append(current_combination)
                return
            
            # 현재 자리에 해당하는 문자들 가져오기
            possible_letters = telephone[digits[index]]
            
            # 각 문자에 대해 재귀적으로 호출
            for letter in possible_letters:
                backtrack(index + 1, current_combination + letter)
        
        result = []
        backtrack(0, "")
        return result

 

 

시간 복잡도: O(3^n)
공간 복잡도: O(n * 3^n)