Đảo Ngược Các Chuỗi Con Giữa Mỗi Cặp Dấu Ngoặc Trong C++

Giả sử chúng ta có một chuỗi s bao gồm các chữ cái thường và dấu ngoặc. Chúng ta phải đảo ngược các chuỗi trong mỗi cặp dấu ngoặc khớp, bắt đầu từ cặp sâu nhất. Kết quả không được chứa dấu ngoặc. Ví dụ, đầu vào "(hel(lowo)rld)" cho đầu ra "dlrlowoleh", quy trình: "(hel(lowo)rld)" → "(helowolrld)" → "dlrowoleh".

Để giải quyết, chúng ta làm theo các bước:

• n := độ dài chuỗi, tạo mảng par kích thước n, định nghĩa stack st.

• Với i từ 0 đến n-1:

  • Nếu s[i] là '(', đẩy i vào st.

  • Ngược lại (s[i] là ')'), j := st.pop(), par[i] := j và par[j] := i.

• Định nghĩa chuỗi rỗng ret.

• Với i := 0, d := 1; i < n; i += d:

  • Nếu s[i] là '(' hoặc ')', thì i := par[i], d := -d; ngược lại nối s[i] vào ret.

• Trả về ret.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void out(vector <int>& v){
        for(int i = 0; i < v.size(); i++){
            cout << v[i] << " " ;
        }
        cout << endl;
    }
    string reverseParentheses(string s) {
        int n = s.size();
        vector <int> par(n);
        stack <int> st;
        for(int i = 0; i < n; i++){
            if(s[i] == '('){
                st.push(i);
            }
            else if(s[i] == ')'){
                int j = st.top();
                st.pop();
                par[i] = j;
                par[j] = i;
            }
        }
        string ret = "";
        for(int i = 0, d = 1; i < n; i += d){
            if(s[i] == '(' || s[i] == ')'){
                i = par[i];
                d = -d;
            }
            else{
                ret += s[i];
            }
        }
        out(par);
        return ret;
    }
};

int main(){
    Solution ob;
    cout << (ob.reverseParentheses("(hel(lowo)rld)"));
}

Đầu vào

"(hel(lowo)rld)"

Đầu ra

13 0 0 0 9 0 0 0 0 4 0 0 0 0 dlrlowoleh