นากกายจัดวงเล็บเปิดปิดเป็นคู่บนรางมิ้นต์ ไม่ให้ค้างเปิด
leetcodealgorithmsbacktrackingpython

LeetCode #22 Generate Parentheses: เปิด-ปิดให้ถูกทุกแบบ

น้องกายEngineering

โจทย์ให้จำนวนเต็ม n แล้วให้สร้างสตริงวงเล็บที่ถูกต้องทั้งหมดที่มีคู่เปิด-ปิดพอดี n คู่ครับ จุดพลาดบ่อยคือสร้างลำดับที่ปิดก่อนเปิดหรือเปิดค้างท้ายสตริง

วิธีที่ 1: Backtracking นับเปิด/ปิด — ค่าเริ่มต้นที่แนะนำ

เก็บตัวนับ open / close ใส่ ( ได้ถ้า open < n ใส่ ) ได้ถ้า close < open เมื่อความยาวถึง 2n เก็บคำตอบ เวลาประมาณ Catalan number ของผลลัพธ์ หน่วยความจำเป็นความลึก O(n) ไม่นับ output

เหมาะกับ whiteboard และโปรดักชันทั่วไป เพราะโค้ดสั้น อธิบายง่าย

วิธีที่ 2: Brute force ทุกสตริงแล้วตรวจความถูกต้อง

สร้างสตริงยาว 2n จากตัวเลือกสองตัว แล้วใช้สแต็กตรวจ validity จำนวนสตริงเป็น 2^(2n) — ใช้สอนแนวคิดได้ แต่ช้าเกินสำหรับ n ที่โต

เหมาะกับมือใหม่ที่ยังไม่คุ้น pruning

วิธีที่ 3: DP / Catalan สร้างจากชิ้นย่อย

dp[i] = ทุกแบบของ i คู่ โดยครอบ dp[j] ข้างในและต่อ dp[i-1-j] ข้างนอก เวลา/หน่วยความจำผูกกับจำนวนคำตอบเช่นกัน อ่านสวยแต่เขียนบนกระดานช้ากว่า backtracking

เหมาะเมื่ออยากโยง Catalan หรือสร้างทีละชั้น

เลือกเมื่อไหร่: สัมภาษณ์/งานจริง → วิธี 1; สอนพื้นฐาน → วิธี 2 แล้วค่อย prune; ชอบสูตรคณิต → วิธี 3

import unittest

def generate_parenthesis(n):
    out = []
    def dfs(s, open_n, close_n):
        if len(s) == 2 * n:
            out.append(s)
            return
        if open_n < n:
            dfs(s + "(", open_n + 1, close_n)
        if close_n < open_n:
            dfs(s + ")", open_n, close_n + 1)
    dfs("", 0, 0)
    return out

class TestGen(unittest.TestCase):
    def test_n1(self):
        self.assertEqual(generate_parenthesis(1), ["()"])
    def test_n2(self):
        self.assertEqual(sorted(generate_parenthesis(2)), sorted(["()()", "(())"]))

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

Recap

  • จำกฎ: เปิดไม่เกิน n และปิดไม่เกินเปิด
  • นับจำนวนคำตอบด้วย Catalan เพื่อประมาณขนาด output
  • ซ้อมอธิบาย pruning บนกระดานก่อนลงโค้ด