2390. Removing Stars From a String

Medium

Description

給定一個包含星號 * 的字串 s。每次操作中，選擇一個星號，移除它左邊最近的非星號字元以及該星號本身。回傳移除所有星號後的字串。

Example:

Input: s = “leet**cod*e” Output: “lecoe”

Intuition#

核心思路：遇到普通字元就 push，遇到星號就 pop，最後堆疊內容即為答案。

星號移除「左邊最近的字元」，這就是堆疊的 LIFO 行為
題目保證操作合法，不會出現空堆疊時遇到星號的情況

Approaches#

1: Stack#

概念: 遍歷字串，普通字元壓入堆疊，星號則彈出棧頂，最後將堆疊內容組合為字串
時間複雜度: O(n)
空間複雜度: 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 模擬堆疊#

概念: 用 StringBuilder 代替堆疊，遇到星號刪除最後一個字元，避免最後額外的 join 操作
時間複雜度: O(n)
空間複雜度: 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: 「消除配對」或「撤銷最近操作」的字串問題，堆疊是首選
關鍵技巧: StringBuilder 本身就可以模擬堆疊行為（append = push, deleteCharAt(last) = pop），效能更好