[LeetCode] 1415. The k-th Lexicographical String of All Happy Strings of Length n (Python)

Problem

Solution

recursive, backtracking

3개 문자중에서 n개 만큼 뽑는 순열문제.

단, str[i] != str[i+1] 이어야한다.

 

 

Code

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        chars = ['a', 'b', 'c']
        li = []

        def happy(cur):
            # 문자열 길이가 n이면 종료
            if len(cur) == n:
                li.append(cur)
                return
            
            for char in chars:
                # 연속된 문자 체크
                if len(cur) == 0 or cur[-1] != char:
                    happy(cur + char)

        happy('')

        if len(li) == 0 or len(li) < k:
            return ''

        li.sort()
        return li[k-1]

 

Complexity

Time Complexity

최대 n 깊이의 재귀 호출 → O(n)

 

Space Complexity

길이 n의 모든 가능한 문자열을 저장하므로, 리스트의 크기는 O(2ⁿ)