給定一個包含星號
*的字串s。每次操作中，選擇一個星號，移除它左邊最近的非星號字元以及該星號本身。回傳移除所有星號後的字串。
Example:
Input: s = “leet**cod*e” Output: “lecoe”
Intuition
TIP
核心思路：遇到普通字元就 push，遇到星號就 pop，最後堆疊內容即為答案。
- 星號移除「左邊最近的字元」，這就是堆疊的 LIFO 行為
- 題目保證操作合法，不會出現空堆疊時遇到星號的情況
Approaches
1. Stack — O(n) / O(n)
- Idea: 遍歷字串，普通字元壓入堆疊，星號則彈出棧頂，最後將堆疊內容組合為字串
- Time:
O(n) - Space:
O(n)
class Solution {
fun removeStars(s: String): String {
val stack = ArrayDeque<Char>()
for (c in s) {
if (c == '*') {
stack.removeLast()
} else {
stack.addLast(c)
}
}
return stack.joinToString("")
}
}⭐ 2. StringBuilder as Stack — O(n) / O(n)
- Idea: 用 StringBuilder 代替堆疊，遇到星號刪除最後一個字元，避免最後額外的 join 操作
- Time:
O(n) - Space:
O(n)
class Solution {
fun removeStars(s: String): String {
val sb = StringBuilder()
for (c in s) {
if (c == '*') {
sb.deleteCharAt(sb.length - 1)
} else {
sb.append(c)
}
}
return sb.toString()
}
}🔑 Takeaways
- Pattern: 「消除配對」或「撤銷最近操作」的字串問題，堆疊是首選
- Key trick: StringBuilder 本身就可以模擬堆疊行為（append = push, deleteCharAt(last) = pop），效能更好