[LeetCode] 1980. Find Unique Binary String (Python)

Problem

 

Solution

brute force

 

1, 0 으로 만들 수 있는 이진법 수 중 n=len(nums) 을 만족하는 배열 중 nums에 존재하지않는 string 반환하는 문제.

 

Code

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        n = len(nums)
        chars = ["1", "0"]

        def generate(n, cur=""):
            if n==0:
                return [cur]
            res = []
            res += generate(n-1, cur + "0")
            res += generate(n-1, cur + "1")
            return res
    
        result = generate(n)
        for r in result:
            if r not in nums:
                return r

 

Complexity

Time Complexity

각 자리마다 1 or 0 을 선택하므로 O(2^n) 이다.

 

Space Complexity

최대 재귀 깊이는 n이므로, 스택 공간은 O(n) 입니다.

결과 리스트는 2n2^n2n 개의 문자열을 저장해야 합니다.

각 문자열의 길이는 n이므로, 리스트의 총 크기는 O(n⋅2n)O(n \cdot 2^n)O(n⋅2n) 이 됩니다.

따라서, 공간복잡도는 O(n⋅2n)O(n \cdot 2^n)O(n⋅2n) 입니다.