ตรวจสอบวงเล็บสมดุลในนิพจน์ ด้วยพื้นที่ O(1) และเวลา O(N²) ใน Python

ตรวจสอบวงเล็บสมดุลแบบประหยัดหน่วยความจำ

กำหนดสตริง str ที่ประกอบด้วยวงเล็บ '(', ')', '{', '}', '[', ']' ต้องการตรวจสอบว่าวงเล็บสมดุลหรือไม่ วงเล็บสมดุลหมายถึง:

• วงเล็บเปิดและปิดเป็นคู่ประเภทเดียวกัน
• วงเล็บปิดตามลำดับที่ถูกต้อง (LIFO)

ตัวอย่าง: {([])} → True

อัลกอริทึม (O(1) space, O(N²) time)

แนวคิดคือใช้ตัวแปรดัชนี i, j และนับ cnt เพื่อติดตามตำแหน่งวงเล็บที่ยังไม่จับคู่ โดยไม่ใช้สแท็กเพิ่มเติม

1. เริ่มต้น cnt = 0, i = 0, j = -1
2. กำหนดฟังก์ชัน solve(s, temp):
   • ลด cnt ลง 1
   • แปลง s เป็นลิสต์
   • ถ้า j > -1 และ s[j] == temp (พบวงเล็บเปิดที่ตรงกัน):
     • ทำเครื่องหมาย s[i] = s[j] = '#'
     • เลื่อน j ย้อนหลังข้าม '#' ที่ประมวลผลแล้ว
     • เพิ่ม i และคืน 1
   • มิฉะนั้นคืน 0
3. ในฟังก์ชันหลัก bracketOrderCheck(s):
   • ถ้า len(s) == 0 คืน True
   • วนลูป while i < len(s):
     • ถ้าตัวอักษรเป็นวงเล็บปิด (}, ), ]) เรียก solve ด้วยวงเล็บเปิดที่ตรงกัน หากคืน 0 ให้คืน False
     • ถ้าเป็นวงเล็บเปิด: อัปเดต j = i, เพิ่ม i และ cnt
   • หลังลูป ถ้า cnt != 0 คืน False (ยังมีวงเล็บเปิดค้าง)
   • คืน True

โค้ดตัวอย่าง Python

cnt = 0
i = 0
j = -1

def solve(s, temp):
    global i, j, cnt
    cnt -= 1
    s = list(s)
    if j > -1 and s[j] == temp:
        s[i] = '#'
        s[j] = '#'
        while j >= 0 and s[j] == '#':
            j -= 1
        i += 1
        return 1
    else:
        return 0

def bracketOrderCheck(s):
    global i, j, cnt
    if len(s) == 0:
        return True
    else:
        ans = False
        while i < len(s):
            if s[i] == '}':
                ans = solve(s, '{')
                if ans == 0:
                    return False
            elif s[i] == ')':
                ans = solve(s, '(')
                if ans == 0:
                    return False
            elif s[i] == ']':
                ans = solve(s, '[')
                if ans == 0:
                    return False
            else:
                j = i
                i += 1
                cnt += 1
        if cnt != 0:
            return False
        return True

print(bracketOrderCheck("{([])}"))  # True

อินพุต / เอาต์พุต

Input:  "{(()[])}"
Output: True