ข้อ 26 · LC394 Decode String (ถอดรหัสสตริง) 🟡

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

ถอดรหัสแบบ k[...] ที่ซ้อนชั้นได้ — เจอ [ คือ "เซฟเกม" เข้า Stack ก่อนมุดดันเจี้ยนชั้นใน

โจทย์ (LC394): กำหนด string ที่ถูกเข้ารหัสมาแล้ว ให้ return string ที่ถอดรหัสแล้ว กฎการเข้ารหัสคือ k[encoded_string] หมายความว่า encoded_string ที่อยู่ในวงเล็บเหลี่ยมจะถูกทำซ้ำเป็นจำนวน k ครั้งพอดี (k เป็นจำนวนเต็มบวกเสมอ) รับประกันว่า input ที่ให้มาถูกต้องเสมอ ไม่มี whitespace เกินมา วงเล็บเหลี่ยมครบคู่เสมอ และตัวเลขในข้อมูลต้นฉบับใช้เป็นตัวคูณ k เท่านั้น (ไม่มีเลขปนกับตัวอักษรแบบ 3a หรือ 2[4]) ความยาวของ string ผลลัพธ์ไม่เกิน 10^5

Example 1

Input:: s = "3[a]2[bc]"
Output:: "aaabcbc"
Explanation:: a ถูกทำซ้ำ 3 ครั้งเป็น "aaa" และ bc ถูกทำซ้ำ 2 ครั้งเป็น "bcbc" ต่อกันได้ "aaabcbc"

Example 2

Input:: s = "3[a2[c]]"
Output:: "accaccacc"
Explanation:: ชั้นในสุด 2[c] ถอดเป็น "cc" รวมกับ a ได้ "acc" หนึ่งชุด แล้วทำซ้ำ 3 ครั้งเป็น "accaccacc"

Example 3

Input:: s = "2[abc]3[cd]ef"
Output:: "abcabccdcdcdef"
Explanation:: abc ทำซ้ำ 2 ครั้ง ต่อด้วย cd ทำซ้ำ 3 ครั้ง แล้วต่อท้ายด้วย ef ที่ไม่ได้เข้ารหัส

Constraints (ข้อจำกัด)

1 <= s.length <= 30
s มีตัวอักษรพิมพ์เล็ก ตัวเลข และวงเล็บเหลี่ยม
ตัวเลขทุกตัวใน s อยู่ในช่วง 1 ถึง 300 (คือตัวคูณ k)
โจทย์รับประกันว่า s เป็น input ที่ถูกต้องเสมอ (วงเล็บครบคู่)

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

ข้อนี้ยกระดับจากการตรวจวงเล็บธรรมดา มาเป็น "ซ้อนชั้น (Nested)" — สิ่งที่ Stack เกิดมาเพื่อปราบโดยเฉพาะ

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

รูปแบบ 3[a] แปลว่าพิมพ์ a 3 รอบ (ได้ "aaa") ความปวดหัวมาเมื่อซ้อนชั้น เช่น 3[a2[c]] — เหมือนตุ๊กตาแม่ลูกดก

หัวใจสำคัญ: มองวงเล็บ [ เหมือน "เซฟเกม" ก่อนลงดันเจี้ยน — พอเจอ [ แปลว่ากำลังมุดเข้าภารกิจย่อยข้างใน ต้องเก็บของเก่าเข้ากระเป๋า (Stack) ไว้ก่อน พอเจอ ] ภารกิจข้างในจบ ค่อยเอาของในกระเป๋าออกมาประกอบกับผลลัพธ์ที่เพิ่งทำเสร็จ

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

ถือของไว้ 2 อย่าง: curr_str (ข้อความปัจจุบัน) กับ curr_num (ตัวคูณปัจจุบัน) แล้วอ่านทีละตัวอักษร:

เจอตัวเลข: สะสมตัวเลขไว้ (ระวังเลขหลายหลัก เช่น 1 กับ 0 ต้องประกอบเป็น 10)
เจอวงเล็บเปิด [ (จุดเซฟเกม): โยน curr_str กับ curr_num ใส่ Stack แล้วเคลียร์มือ (curr_str = "", curr_num = 0) เพื่อลุยข้อความด้านใน
เจอตัวอักษร: ต่อท้าย curr_str ไปเรื่อย ๆ
เจอวงเล็บปิด ] (จบดันเจี้ยน): ดึงของที่เซฟไว้ล่าสุดจาก Stack ได้ข้อความเก่ากับตัวคูณ แล้วประกอบ: ข้อความเก่า + (ข้อความปัจจุบัน × ตัวคูณ)

3. โค้ด Python (LeetCode Ready)

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

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        curr_str = ""
        curr_num = 0

        for char in s:
            if char.isdigit():
                # กฎข้อ 1: สะสมตัวเลข (คูณ 10 เพื่อดันหลัก เช่น 1 → 12)
                curr_num = (curr_num * 10) + int(char)

            elif char == '[':
                # กฎข้อ 2: เซฟเกม! โยนข้อความและตัวคูณใส่ Stack
                stack.append((curr_str, curr_num))
                # เคลียร์มือให้ว่างเพื่อลุยข้อความในวงเล็บ
                curr_str = ""
                curr_num = 0

            elif char == ']':
                # กฎข้อ 4: จบวงเล็บ ดึงของที่เซฟไว้ออกมา
                prev_str, multiplier = stack.pop()
                # ข้อความเก่า ต่อด้วย ข้อความใหม่ที่โดนคูณ
                curr_str = prev_str + (curr_str * multiplier)

            else:
                # กฎข้อ 3: เจอตัวอักษรปกติ ก็พิมพ์สะสมไปเรื่อย ๆ
                curr_str += char

        return curr_str

4. จำลองการทำงาน — s = "3[a]2[bc]"

อักขระ	curr_num	curr_str	stack	คำอธิบาย
3	3	""	[]	สะสมตัวเลข
[	0	""	[("", 3)]	ฝากข้อความเก่าและตัวเลขลง stack, รีเซ็ตค่า
a	0	"a"	[("", 3)]	ต่ออักษรธรรมดา
]	0	"aaa"	[]	pop ("", 3) ออกมา → "" + ("a" × 3)
2	2	"aaa"	[]	สะสมตัวเลข
[	0	""	[("aaa", 2)]	ฝากข้อความเก่าและตัวเลขลง stack, รีเซ็ตค่า
b	0	"b"	[("aaa", 2)]	ต่ออักษรธรรมดา
c	0	"bc"	[("aaa", 2)]	ต่ออักษรธรรมดา
]	0	"aaabcbc"	[]	pop ("aaa", 2) ออกมา → "aaa" + ("bc" × 2)

จบเกม — ได้คำตอบ "aaabcbc"

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

เคสสำคัญที่สุด: "เลขหลายหลัก" — บรรทัดนี้มีไว้เพื่อประกอบร่างตัวเลขที่มีมากกว่า 1 หลัก (เช่น 12, 100, หรือ 305) ให้กลายเป็นตัวเลขที่ถูกต้อง:

python

if char.isdigit():
    curr_num = (curr_num * 10) + int(char)

ทำไมต้องเขียนแบบนี้? ทำไมไม่ใช้แค่ curr_num = int(char)?

เพราะลูป for char in s: อ่านอักขระทีละตัว (เป็น string) ถ้าโจทย์ให้ตัวเลขมากกว่า 1 หลัก เช่น 12[a] คอมพิวเตอร์จะเห็น '1' ก่อน แล้วรอบถัดไปค่อยเห็น '2'

หากเขียนแค่ curr_num = int(char):

รอบแรกเจอ '1' → curr_num = 1
รอบสองเจอ '2' → curr_num โดนทับกลายเป็น 2 (ผิด! จริง ๆ ต้องเป็นสิบสอง)

หลักการของสูตร (curr_num * 10) + int(char): คูณ 10 เพื่อเลื่อนหลักไปทางซ้าย แล้วบวกเลขตัวใหม่ — สมมติโจทย์คือ 123[a]:

รอบที่ 1 เจอ '1' (เริ่มจาก curr_num = 0): (0 × 10) + 1 = 1
รอบที่ 2 เจอ '2': (1 × 10) + 2 = 12 (เลข 1 เดิมถูกดันขึ้นเป็นหลักสิบ)
รอบที่ 3 เจอ '3': (12 × 10) + 3 = 123 (เลข 12 เดิมถูกดันขึ้นเป็นหลักร้อยและหลักสิบ)

สรุปสั้น ๆ

พอเจอวงเล็บเปิด [ ต่อ ระบบก็ได้ตัวเลข 123 ที่สมบูรณ์พร้อมเอาไปใช้งาน — ทริกคูณ 10 คืออาวุธสำคัญเวลาเลขมีหลายหลัก

เคส "ไม่มีวงเล็บเลย" — s = "abc": แค่ต่อ curr_str ไปเรื่อย ๆ จนจบ ไม่แตะ Stack เลย ก็ถูกต้อง

6. Time & Space Complexity

Time O(ความยาวผลลัพธ์) — อ่าน s รอบเดียว แต่ตอนสั่ง "acc" * 3 คอมพิวเตอร์ต้องสร้างสตริงยาวจริง
Space O(ความลึกของวงเล็บ) — ซ้อนลึกมาก เช่น 3[2[4[5[a]]]] ต้องเซฟสถานะใน Stack ลึกตามไปด้วย

💡 สรุป pattern

โจทย์ที่มีโครงสร้าง nested (ซ้อนชั้น) เช่น วงเล็บ / expression / tag — push สถานะชั้นนอกเก็บไว้ก่อนดำเข้าชั้นใน แล้ว pop กลับมาประกอบเมื่อชั้นในจบ