Description
給定一個字串陣列
nums，包含n個長度為n的互不相同的二進位字串。回傳一個長度為n且不在nums中的二進位字串（保證至少存在一個答案）。
Example:
Input: nums = [“01”,“10”] Output: “11”
Intuition#
核心思路：用 Cantor 對角線法，第 i 位取 nums[i] 第 i 位的反，保證結果與每個字串至少一位不同。
- n 個長度為 n 的字串，共有 2^n 種可能，必定有至少一個不在其中
- Cantor 對角線法：構造字串
result[i] = flip(nums[i][i]) - 這保證 result 與 nums[i] 至少在第 i 位不同，所以 result 不等於任何 nums[i]
Approaches#
1: 回溯 / 暴力搜索#
- 概念: 用 HashSet 存所有 nums，嘗試構造每個可能的二進位字串直到找到不在集合中的
- 時間複雜度:
O(2^n * n)最差情況 - 空間複雜度:
O(n^2)
class Solution {
fun findDifferentBinaryString(nums: Array<String>): String {
val set = nums.toHashSet()
val n = nums[0].length
fun backtrack(current: StringBuilder): String? {
if (current.length == n) {
val s = current.toString()
return if (s !in set) s else null
}
for (bit in charArrayOf('0', '1')) {
current.append(bit)
val result = backtrack(current)
if (result != null) return result
current.deleteCharAt(current.lastIndex)
}
return null
}
return backtrack(StringBuilder())!!
}
}⭐2: Cantor 對角線法#
- 概念: 第 i 位取 nums[i][i] 的反，保證構造出的字串與每個 nums[i] 都不同
- 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun findDifferentBinaryString(nums: Array<String>): String {
val sb = StringBuilder()
for (i in nums.indices) {
sb.append(if (nums[i][i] == '0') '1' else '0')
}
return sb.toString()
}
}🔑 Takeaways#
- Pattern: 構造不在集合中的元素 → Cantor 對角線法
- 關鍵技巧: 對角線法的核心保證——result[i] != nums[i][i]，所以 result 與任何 nums[i] 至少有一位不同；這是一個數學 / 構造性的 O(n) 解法，比回溯優雅得多