LeetCode #394 Decode String: แกะวงเล็บซ้อนด้วย stack

Decode String ให้ถอดรูปแบบ k[encoded_string] ซึ่งวงเล็บซ้อนกันได้ เช่น 3[a2[c]] กลายเป็น accaccacc ครับ ตัวเลขอาจมีหลายหลัก จึงห้ามอ่านทีละ digit แล้วคิดว่าเป็นจำนวนรอบทันที

วิธี 1: ขยายวงเล็บชั้นในสุดซ้ำ ๆ

หา [ ตัวสุดท้าย จับคู่ ] ตัวแรกหลังมัน อ่านเลขด้านหน้าแล้วแทนช่วงนั้นด้วยข้อความที่ขยาย ทำจนไม่มีวงเล็บ แนวคิดตรงเหมือนแกะกล่องจากใบเล็กสุด แต่การสร้าง string ซ้ำหลายรอบอาจคัดลอกข้อมูลมาก เวลาแย่ได้ถึง O(n × output) และหาตำแหน่งเลขหลายหลักต้องระวัง เหมาะเป็น prototype มากกว่าคำตอบหลัก

วิธี 2: explicit stack รอบเดียว

เก็บข้อความก่อนเข้า [ และจำนวนรอบไว้ใน stack เมื่อเจอ ] ให้นำข้อความปัจจุบันคูณแล้วต่อกลับ โครงสร้างนี้เหมือนฝากตะกร้าชั้นนอกไว้หน้าห้อง ก่อนเข้าไปจัดของในกล่องชั้นใน เวลา O(n + output) พื้นที่ O(depth + output) และไม่เสี่ยง call stack เป็น default ที่พกข้ามภาษาได้ดี

วิธี 3: recursive descent parser

ให้ฟังก์ชันอ่านจนเจอ ] แล้วคืนข้อความพร้อมตำแหน่งถัดไป โค้ดตาม grammar และต่อยอด validation ได้ง่าย เวลา O(n + output) แต่ใช้ call stack O(depth) ถ้า nesting ลึกผิดปกติ explicit stack ปลอดภัยกว่า

from __future__ import annotations

import unittest


def decode_stack(text: str) -> str:
    stack: list[tuple[list[str], int]] = []
    current: list[str] = []
    repeat = 0
    for char in text:
        if char.isdigit():
            repeat = repeat * 10 + int(char)
        elif char == "[":
            stack.append((current, repeat))
            current, repeat = [], 0
        elif char == "]":
            parent, count = stack.pop()
            current = parent + current * count
        else:
            current.append(char)
    return "".join(current)


def decode_recursive(text: str) -> str:
    def parse(index: int) -> tuple[str, int]:
        out: list[str] = []
        repeat = 0
        while index < len(text) and text[index] != "]":
            if text[index].isdigit():
                repeat = repeat * 10 + int(text[index])
                index += 1
            elif text[index] == "[":
                nested, index = parse(index + 1)
                out.append(nested * repeat)
                repeat = 0
            else:
                out.append(text[index])
                index += 1
        return "".join(out), index + 1

    return parse(0)[0]


class DecodeStringTests(unittest.TestCase):
    def test_stack_and_recursive_parser(self):
        cases = {"3[a]2[bc]": "aaabcbc", "3[a2[c]]": "accaccacc", "10[z]": "z" * 10, "abc": "abc"}
        for encoded, expected in cases.items():
            self.assertEqual(decode_stack(encoded), expected)
            self.assertEqual(decode_recursive(encoded), expected)


if __name__ == "__main__":
    unittest.main()

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static String decode(String text) {
        Deque<StringBuilder> strings = new ArrayDeque<>();
        Deque<Integer> counts = new ArrayDeque<>();
        StringBuilder current = new StringBuilder();
        int repeat = 0;
        for (char ch : text.toCharArray()) {
            if (Character.isDigit(ch)) {
                repeat = repeat * 10 + (ch - '0');
            } else if (ch == '[') {
                strings.push(current);
                counts.push(repeat);
                current = new StringBuilder();
                repeat = 0;
            } else if (ch == ']') {
                String nested = current.toString();
                current = strings.pop();
                current.append(nested.repeat(counts.pop()));
            } else {
                current.append(ch);
            }
        }
        return current.toString();
    }

    public static void main(String[] args) {
        assert decode("3[a]2[bc]").equals("aaabcbc");
        assert decode("3[a2[c]]").equals("accaccacc");
        assert decode("10[z]").equals("zzzzzzzzzz");
        System.out.println("3 assertions passed");
    }
}

Edge cases ที่ต้องลอง

• ตัวคูณหลายหลัก เช่น 10[z]
• วงเล็บซ้อน เช่น 2[a3[b]]
• ตัวอักษรธรรมดาก่อนและหลังกลุ่ม
• input ที่ไม่มีวงเล็บ
• output ใหญ่มาก แม้ input สั้น: production ควรกำหนด output limit เพื่อกัน memory exhaustion

Decision table

เงื่อนไข	ขยายชั้นในสุด	Explicit stack	Recursive parser
input/nesting ใหญ่	ช้า	ดีที่สุด	เสี่ยง call stack
extra memory	string ชั่วคราวมาก	O(depth + output)	stack + output
readability	เห็นภาพง่าย	ชัดในหลายภาษา	ตรง grammar
sorted input	ไม่เกี่ยว	ไม่เกี่ยว	ไม่เกี่ยว
streaming	อ่าน input ทีละ char ได้ แต่ output ยังอาจใหญ่	เหมาะสุดแต่ต้อง buffer กลุ่มซ้อน	ต้องรักษา call state
mutation input	ไม่มี	ไม่มี	ไม่มี

ผมเลือก explicit stack เป็น default เพราะคุม nesting เอง อ่านตัวคูณหลายหลักได้ในรอบเดียว และไม่ผูกความถูกต้องกับ recursion limit ถ้ากำลังสร้าง parser ที่ต้องรายงาน syntax error ละเอียด recursive descent จะต่อยอดง่ายกว่า

Recap

• สะสมเลขด้วย repeat = repeat * 10 + digit
• ฝากทั้งข้อความชั้นนอกและจำนวนรอบเมื่อเจอ [
• ระวัง output โตแบบทวีคูณและกำหนด limit ในระบบจริง
• เทสต์ข้อความธรรมดา ตัวคูณหลายหลัก และวงเล็บซ้อน