ย้อนกลับสตริงย่อยระหว่างวงเล็บแต่ละคู่ใน C++

สมมติว่าเรามีสตริงที่ประกอบด้วยตัวพิมพ์เล็กและวงเล็บ เราต้องกลับสตริงในวงเล็บที่ตรงกันแต่ละคู่โดยเริ่มจากวงในสุด และผลลัพธ์ไม่ควรมีวงเล็บ ดังนั้นหากอินพุตเป็นเหมือน "(hel(lowo)rld)" ผลลัพธ์จะเป็น "dlrlowoleh" ดังนั้นจากจุดเริ่มต้นจะเปลี่ยนเป็น:"(hel(lowo)rld)" → "(helowolrld)" → “ดลโรโวเลห์”.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของสตริง สร้างอาร์เรย์ที่เรียกว่า par ซึ่งมีความยาวเป็น n กำหนด stack st

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • ถ้า s[i] เปิดวงเล็บ ให้ใส่ i ลงใน st

  • มิฉะนั้น เมื่อ s[i] ปิดวงเล็บ ดังนั้น j :=st.pop(), par[i] :=j และ par[j] :=i

• กำหนดหนึ่งสตริงว่าง ret

• สำหรับ i :=0, d :=1, i

  • ถ้า s[i] กำลังเปิดวงเล็บหรือ s[i] กำลังปิดวงเล็บ ดังนั้น i :=par[i], d :=-d มิฉะนั้นให้เพิ่ม ret โดย s[i]

• รีเทิร์น

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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;
   }
};
main(){
   Solution ob;
   cout << (ob.reverseParentheses("(hel(lowo)rld)"));
}

อินพุต

"(hel(lowo)rld)"

ผลลัพธ์

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