LeetCode Valid Parentheses: สแต็กกับการจับคู่เครื่องหมาย

โจทย์ให้สตริงที่มีแค่ ()[]{} แล้วถามว่าเครื่องหมายเปิดปิดจับคู่และลำดับถูกต้องหรือไม่ เช่น "()[]{}" ผ่าน แต่ "(]" ไม่ผ่าน

แนวทางที่ 1: นับอย่างเดียว (ไม่พอ)

นับจำนวนเปิดกับปิดเท่ากันยังไม่พอ เพราะ ")(" นับเท่ากันแต่ผิด วิธีนี้ใช้สอนจุดพลาดได้ แต่ไม่ใช่คำตอบ

แนวทางที่ 2: สแต็กคลาสสิก (แนะนำหลัก)

เจอเปิดให้ดันเข้า stack เจอปิดให้ดูว่าบนสุดของ stack เป็นคู่เปิดที่ถูกหรือไม่ ถ้าไม่ตรงหรือ stack ว่าง ให้ไม่ผ่าน จบแล้ว stack ต้องว่าง

นี่เป็นตัวอย่างโค้ดแบบ fragment / pseudocode สำหรับอธิบายแนวคิด:

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return not stack

• เวลา O(n) พื้นที่ O(n)
• อธิบายง่าย ตรงกับโครงสร้างข้อมูลพื้นฐาน

แนวทางที่ 3: แทนที่ซ้ำ ๆ

วนแทนที่ "()", "[]", "{}" ด้วยสตริงว่างจนหมดหรือไม่เปลี่ยน

• เข้าใจง่ายมาก แต่เวลาแย่ลงเมื่อสตริงยาว เพราะสร้างสตริงใหม่บ่อย
• เหมาะสาธิตแนวคิด ไม่เหมาะคำตอบหลักในสัมภาษณ์จังหวะจบ

แนวทางที่ 4: ตารางคู่แบบแมป

เหมือนสแต็ก แต่แยกแมปเปิดถึงปิดหรือปิดถึงเปิดให้ชัด ลด if ยาว ช่วยลดบั๊กตอนเขียนเร็ว

แนวทางที่ 5: พาร์เซอร์จริงในโปรดักชัน

ถ้าเป็นตัวตรวจนิพจน์จริง อาจใช้ไลบรารีพาร์เซอร์หรือ grammar แต่สำหรับโจทย์ LeetCode สแต็กยังสั้นและถูกที่สุด

แผนภาพด้านล่างเป็น fragment / pseudocode ของลำดับตรวจ:

flowchart TD
  A[อ่านตัวอักษร] --> B{เปิดหรือปิด?}
  B -->|เปิด| C[push เข้า stack]
  B -->|ปิด| D{บนสุดเป็นคู่ถูก?}
  D -->|ไม่| E[ไม่ผ่าน]
  D -->|ใช่| F[pop]
  C --> A
  F --> A
  A --> G{หมดสตริงและ stack ว่าง?}
  G -->|ใช่| H[ผ่าน]
  G -->|ไม่| E

เลือกใช้เมื่อไหร่

สถานการณ์	แนะนำ
มือใหม่	วาด stack บนกระดาษกับตัวอย่างสั้น
ไวท์บอร์ด	สแต็ก + แมปคู่
โปรดักชันตรวจสตริงสั้นมาก	สแต็กเดียวกัน หรือรีใช้ไลบรารีถ้ามีกฎซับซ้อน

Recap

• นับอย่างเดียวไม่พอ ต้องรักษาลำดับด้วย stack
• จบแล้ว stack ต้องว่าง
• เตรียมเคสสตริงว่าง ปิดก่อนเปิด และคู่คนละชนิด
• พูด tradeoff พื้นที่ O(n) กับความถูกต้องให้ครบครับ