ข้อ 24 · LC2390 Removing Stars From a String (ลบดาวจากสตริง) 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

โจทย์ Stack แบบย้อนรอย (Undo / Backspace) — เจอ * ให้ลบตัวอักษรซ้ายที่ใกล้ที่สุด

โจทย์ (LC2390): กำหนด string s ที่มีเครื่องหมายดาว * ปนอยู่ ในหนึ่ง operation ให้เลือกดาวตัวหนึ่งใน s แล้วลบ character ที่ไม่ใช่ดาวตัวที่อยู่ใกล้ทางซ้ายของมันที่สุดออก พร้อมกับลบดาวตัวนั้นทิ้งไปด้วย ให้ return string ที่เหลือหลังลบดาวออกจนหมดทุกตัว (input ที่ให้มารับประกันว่า operation ทำได้เสมอ)

Example 1

Input:: s = "leet**cod*e"
Output:: "lecoe"
Explanation:: ลบจากซ้ายไปขวา: ดาวตัวแรกลบ t ได้ "lee*cod*e" ดาวตัวที่สองลบ e ได้ "lecod*e" ดาวตัวสุดท้ายลบ d ได้ "lecoe"

Example 2

Input:: s = "erase*****"
Output:: ""
Explanation:: ดาวลบตัวอักษรไปเรื่อย ๆ จนหมดทั้ง string เหลือ string ว่าง

Example 3

Input:: s = "ab*c"
Output:: "ac"
Explanation:: ดาวลบ b ซึ่งเป็นตัวที่ใกล้ทางซ้ายที่สุด เหลือ "ac"

Constraints (ข้อจำกัด)

1 <= s.length <= 10^5
s มีตัวอักษรพิมพ์เล็กและเครื่องหมาย *
โจทย์รับประกันว่าการลบทำได้เสมอ (ไม่มี * เกินจำนวนตัวอักษร)

เฉลยเต็ม · ซ่อนไว้ให้ลองเองก่อนพับไว้ด้านใน — คลิกเมื่อพร้อมดู

ข้อนี้ตรงกับประโยคท่องจำของหมวด Stack เป๊ะ: "การย้อนรอย (Undo / Backspace)"

1. ปลดล็อกไอเดีย (Mindset Shift)

โจทย์บอกว่าถ้าเจอเครื่องหมายดาว * ให้ลบตัวอักษรที่อยู่ "ซ้ายมือที่ใกล้ที่สุด" ทิ้งไป 1 ตัว พร้อมกับลบดาวทิ้งด้วย

หัวใจสำคัญ: มองเครื่องหมาย * เป็นปุ่ม Backspace บนคีย์บอร์ด — เวลาพิมพ์ผิดเรากด Backspace เพื่อลบตัวอักษรตัวล่าสุดที่เพิ่งพิมพ์ ซึ่งคอนเซปต์นี้เกิดมาเพื่อ Stack โดยตรง

2. กฎเหล็ก 3 ข้อ (The Logic)

จำลองว่ามีกระป๋องว่าง ๆ (Stack) อยู่ 1 ใบ แล้วอ่านตัวอักษรทีละตัวจากซ้ายไปขวา:

เจอตัวอักษรปกติ (a-z): หย่อนลงกระป๋อง (append) — เหมือนกำลังพิมพ์
เจอเครื่องหมายดาว *: ดึงของชิ้นบนสุดในกระป๋องทิ้ง 1 ชิ้น (pop) — เหมือนกด Backspace ลบตัวล่าสุด
จบเกม: เอาตัวอักษรที่เหลือรอดในกระป๋องมาเทต่อกันเป็นข้อความ ("".join) แล้วส่งคำตอบ

3. โค้ด Python (LeetCode Ready)

โค้ดข้อนี้สั้นและตรงไปตรงมา:

คำตอบสำหรับวางใน LeetCodepython

class Solution:
    def removeStars(self, s: str) -> str:
        stack = []

        for char in s:
            # กฎข้อ 2: เจอรูปดาว = กด Backspace ลบตัวล่าสุดทิ้ง
            if char == '*':
                stack.pop()
            # กฎข้อ 1: เจอตัวอักษร = พิมพ์เก็บใส่ Stack
            else:
                stack.append(char)

        # กฎข้อ 3: เอาตัวอักษรที่เหลือมาเชื่อมเป็น String เดียว
        # "".join() เปลี่ยน list เช่น ['a', 'b'] ให้เป็น "ab"
        return "".join(stack)

4. จำลองการทำงาน — s = "leet**cod*e"

อ่าน	ทำอะไร	stack หลังทำ
l	โยนลงกระป๋อง	['l']
e	โยนลงกระป๋อง	['l', 'e']
e	โยนลงกระป๋อง	['l', 'e', 'e']
t	โยนลงกระป๋อง	['l', 'e', 'e', 't']
*	กดลบ! ดึง t ทิ้ง	['l', 'e', 'e']
*	กดลบอีกรอบ! ดึง e ทิ้ง	['l', 'e']
c	โยนลงกระป๋อง	['l', 'e', 'c']
o	โยนลงกระป๋อง	['l', 'e', 'c', 'o']
d	โยนลงกระป๋อง	['l', 'e', 'c', 'o', 'd']
*	กดลบ! ดึง d ทิ้ง	['l', 'e', 'c', 'o']
e	โยนลงกระป๋อง	['l', 'e', 'c', 'o', 'e']
(จบ)	"".join(stack)	"lecoe"

จบสแกนข้อความแล้วจับมัดรวมด้วย "".join(stack) ได้คำตอบ "lecoe" ถูกต้องเป๊ะ

5. จุดระวังตกหลุมพราง (Edge Cases)

เคส "ดาวรัว ๆ" — สมมติ s = "ab**":

ใส่ a, ใส่ b → กระป๋องมี ['a', 'b']
เจอ * ตัวแรก ลบ b ทิ้ง → ['a']
เจอ * ตัวสอง ลบ a ทิ้ง → []
ตอนสุดท้าย "".join([]) ได้ข้อความว่าง "" — โค้ดรับมือได้

ข้อควรรู้เรื่อง pop บนกระป๋องว่าง

ในความเป็นจริง ถ้ากระป๋องว่างแล้วไปกด pop() โค้ดจะพัง แต่โจทย์ข้อนี้การันตีว่า "The operation is always possible" — ไม่มีทางเจอดาวตอนกระป๋องว่าง จึงไม่ต้องเขียน if stack: ดักไว้

6. Time & Space Complexity

Time O(n) — เดินอ่านข้อความทีละตัวรอบเดียว · append / pop เป็น O(1)
Space O(n) — จอง stack เก็บตัวอักษร · กรณีแย่สุดไม่มีดาวเลย ต้องเก็บครบทุกตัว

💡 สรุป pattern

เมื่อโจทย์บอกให้ "ลบ/จับคู่กับตัวล่าสุดที่ยังเหลือ" ให้นึกถึง stack ทันที — push ตอนเจอของ · pop ตอนเจอสัญญาณลบ (ที่นี่ * = Backspace)