Description
給定一個長度為
2n的字串s，只包含[和]，且各有n個。你可以交換任意兩個位置的字元，回傳使字串成為合法括號字串所需的最少交換次數。
Example:
Input: s = “][]” Output: 1 （交換 index 0 和 index 3 得到 “[[]]"）
Intuition#
核心思路：消除所有已配對的括號後，剩下的一定是
]]]...[[[形式。若剩餘未配對的]有k個，則最少交換次數為⌈k/2⌉。
- 遍歷字串，用計數器模擬 Stack：遇到
[加 1，遇到]若有未配對的[就消掉，否則記錄多餘的] - 消除配對後，剩下的未配對
]數量為unmatched - 每次交換可以修復 2 個未配對（一個
]變成正確位置的[，對應的另一端也修好），所以答案是⌈unmatched / 2⌉
Approaches#
1: Stack Simulation#
- 概念: 用 Stack 消除配對括號，最後 Stack 中剩餘的就是未配對的括號數
- 時間複雜度:
O(n)- 遍歷一次字串 - 空間複雜度:
O(n)- Stack 最壞存 n 個字元
class Solution {
fun minSwaps(s: String): Int {
val stack = ArrayDeque<Char>()
for (c in s) {
if (c == '[') {
stack.addLast(c)
} else {
if (stack.isNotEmpty() && stack.last() == '[') {
stack.removeLast()
} else {
stack.addLast(c)
}
}
}
// stack 中剩餘的是交替的 ]...[ ，未配對的 ] 數量 = stack.size / 2
val unmatched = stack.size / 2
return (unmatched + 1) / 2
}
}⭐2: Greedy Counter (O(1) Space)#
- 概念: 不用 Stack，只追蹤目前未配對的
]數量（close計數器）。遇到[時若有未配對]就消掉，否則不管；遇到]時若無[可配對就累加 - 時間複雜度:
O(n)- 遍歷一次字串 - 空間複雜度:
O(1)- 只用常數變數
class Solution {
fun minSwaps(s: String): Int {
var unmatched = 0 // 未配對的 ] 數量
var open = 0 // 可用的 [ 數量
for (c in s) {
if (c == '[') {
open++
} else {
if (open > 0) {
open--
} else {
unmatched++
}
}
}
return (unmatched + 1) / 2
}
}為什麼
⌈k/2⌉？消除配對後剩下]]]...[[[，每次交換最外層的一對]和[可以修復 2 個未配對。例如]][[只需 1 次交換變成[[][]]或[[]]。
🔑 Takeaways#
- Pattern: 括號配對問題 -> Stack 或計數器消除配對，再處理剩餘部分
- 關鍵技巧: 未配對括號的最少交換公式
⌈k/2⌉是 Greedy 結論，每次交換修復兩個未配對