ตรวจสอบวงเล็บสมดุล O(1) space O(N²) time ใน C++

แนวคิด

กำหนดสตริง str ประกอบด้วย '(', ')', '{', '}', '[', ']' ต้องการตรวจสอบว่าวงเล็บสมดุลหรือไม่ โดยใช้พื้นที่ O(1) และเวลา O(N²)

วงเล็บสมดุลหมายถึง: วงเล็บเปิดต้องปิดด้วยประเภทเดียวกัน และเรียงลำดับถูกต้อง

วิธีการแก้ปัญหา

• ใช้ตัวแปร a, b ติดตามตำแหน่งวงเล็บเปิด-ปิดที่กำลังเปรียบเทียบ
• นับ count: เพิ่มเมื่อเจอวงเล็บเปิด, ลดเมื่อเจอวงเล็บปิด
• เจอวงเล็บเปิด: b=a, a=a+1, count++
• เจอวงเล็บปิด: ลด count, เปรียบเทียบวงเล็บที่ i กับ j
  • ถ้าตรงกัน: แทนที่ '#' ในตำแหน่ง a,b, ขยับ a++, b-- ข้าม '#' จนกว่าจะเจอตัวอักษรปกติ
  • ถ้าไม่ตรง: return false
• สุดท้ายถ้า count != 0 → false

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

#include <iostream>
using namespace std;

bool helperFunc(int& count1, string& s1, int& i1, int& j1, char tocom1){
    count1--;
    if (j1 > -1 && s1[j1] == tocom1) {
        s1[i1] = '#';
        s1[j1] = '#';
        while (j1 >= 0 && s1[j1] == '#') j1--;
        i1++;
        return 1;
    }
    else return 0;
}

bool isValid(string s1){
    if (s1.length() == 0) return true;
    else {
        int i1 = 0;
        int count1 = 0;
        int j1 = -1;
        bool result1;
        while (i1 < s1.length()) {
            switch (s1[i1]) {
                case '}':
                    result1 = helperFunc(count1, s1, i1, j1, '{');
                    if (result1 == 0) return false;
                    break;
                case ')':
                    result1 = helperFunc(count1, s1, i1, j1, '(');
                    if (result1 == 0) return false;
                    break;
                case ']':
                    result1 = helperFunc(count1, s1, i1, j1, '[');
                    if (result1 == 0) return false;
                    break;
                default:
                    j1 = i1;
                    i1++;
                    count1++;
            }
        }
        if (count1 != 0) return false;
        return true;
    }
}

int main(){
    string str1 = "[[]][]()";
    if (isValid(str1))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

ผลลัพธ์

Yes