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

 

 

난이도: Medium

문제 설명

---

Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.

 

문제 예제

---

Example 1:

Input: nums = ["01","10"]
Output: "11"
Explanation: "11" does not appear in nums. "00" would also be correct.

Example 2:

Input: nums = ["00","01"]
Output: "11"
Explanation: "11" does not appear in nums. "10" would also be correct.

Example 3:

Input: nums = ["111","011","001"]
Output: "101"
Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.

 

제한 사항

---

• n == nums.length
• 1 <= n <= 16
• nums[i].length == n
• nums[i] is either '0' or '1'.
• All the strings of nums are unique.

 

✏️ Solution(솔루션)

---

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        n = len(nums)
        answer = ''
        
        def backtracking(now, len_now):
            if len_now == n:
                return '' if now in nums else now

            for i in ['0', '1']:
                answer = backtracking(now+i, len_now+1)
                if answer != '':
                    return answer
            
            return answer
        
        return backtracking('',0)

 

이 문제는 전날 풀었던 1415. The k-th Lexicographical String of All Happy Strings of Length n와 같은 방식이었다.

 

backtracking을 통해 0과 1을 통해 가능한 이진수를 만들어주었다.

 

현재 만들어진 이진수의 길이가 n과 같아지면 nums의 이 이진수가 있는지 없는지 판단하였다.

 

만약 있으면 만들어진 이진수를 그대로 return 하였고 아니면 ''을 return 하였다.

 

문제에서 가능한 이진수가 여러개 있으면 그중 아무거나 반환하라고 했으니 맨 처음 조건을 만족하는 이진수를 바로 반환하였고 정답을 맞출 수 있었다.

 

⚙️ Runtime & Memory

---

 

 

---

문제: 1980. Find Unique Binary String

 

깃허브: github

algorithmPractice/LeetCode/2107-find-unique-binary-string at main · laewonJeong/algorithmPractice