[LeetCode] 1980. Find Unique Binary String

 轉自LeetCode

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.

 

Constraints:

• 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

使用和 41. First Missing Positive 的解題方式可以成功

改變的地方是要把 binary string 變成 int ( Kotlin 可以用 value  = Integer.parseInt(string, 2) )

然後把值放到 index = value 即可

不過看到討論裡面有個神解，真的太猛

因為題目限制的關係，binary string 的長度，會和 nums.size 是一樣長

所以，從每一個 binary string 裡面，拿一個值出來，反轉 (0 -> 1 or 1 -> 0) 加到答案

歷遍完，就找到答案了

而為什麼一定會成功，因為最後的答案，和 nums 裡面的每一個 binary string

一定至少會有一個 bit 是不一樣的，所以最終的答案，一定不在 nums 裡面，也是要找的

圖解，以 nums = ["111", "001", "010"] 為例

Kotlin

	class Solution {
	fun findDifferentBinaryString(nums: Array<String>): String {
	var ans = ""
	for(i in nums.indices) {
	ans = if (nums[i][i] == '0') {
	ans + "1"
	} else {
	ans + "0"
	}
	}
	return ans
	}
	}

view raw find_unique_binary_string.kt hosted with ❤ by GitHub