1980. Find Unique Binary String - Explanation

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        strSet = {s for s in nums}

        def backtrack(i, cur):
            if i == len(nums):
                res = "".join(cur)
                return None if res in strSet else res

            res = backtrack(i + 1, cur)
            if res: return res

            cur[i] = "1"
            return backtrack(i + 1, cur)

        return backtrack(0, ["0" for _ in nums])

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        strSet = set(nums)
        n = len(nums)

        for num in range(1 << n):
            res = bin(num)[2:].zfill(n)
            if res not in strSet:
                return res

        return ""

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        res = []
        for i in range(len(nums)):
            if nums[i][i] == '0':
                res.append('1')
            else:
                res.append('0')
        return "".join(res)

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        strSet = set(nums)
        n = len(nums)

        while True:
            res = "".join(random.choice("01") for _ in range(n))
            if res not in strSet:
                return res

class Node:
    def __init__(self):
        self.children = [None, None]

    def contains_bit(self, bit: int) -> bool:
        return self.children[bit] is not None

    def put(self, bit: int):
        self.children[bit] = Node()

    def get(self, bit: int):
        return self.children[bit]

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, s: str):
        curr = self.root
        for c in s:
            bit = int(c)
            if not curr.contains_bit(bit):
                curr.put(bit)
            curr = curr.get(bit)

    def search(self, res: str, curr) -> bool:
        while curr.contains_bit(0) or curr.contains_bit(1):
            if not curr.contains_bit(0):
                res.append('0')
                return True
            if not curr.contains_bit(1):
                res.append('1')
                return True

            res.append('1')
            curr = curr.get(1)

        return False

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        trie = Trie()
        for s in nums:
            trie.insert(s)

        res = []
        trie.search(res, trie.root)

        while len(res) < len(nums):
            res.append('1')

        return ''.join(res)