การขยายวงเล็บปีกกาใน C ++

สมมติว่าเรามีสตริง S ที่แสดงถึงรายการคำ ที่นี่แต่ละตัวอักษรในคำมี 1 ตัวเลือกขึ้นไป หากมีเพียงตัวเลือกเดียว จดหมายจะแสดงตามที่เป็นอยู่ หากมีมากกว่าหนึ่งตัวเลือก วงเล็บปีกกาจะกำหนดตัวเลือก ตัวอย่างเช่น "{a,b,c}" จะแสดงตัวเลือก ["a", "b", "c"] ตัวอย่างเช่น หากอินพุตเป็น "{a,b,c}d{e,f}" จะแสดงรายการ ["ade", "adf", "bde", "bdf", "cde", "cdf"].

ส่งกลับคำทั้งหมดที่เกิดขึ้นในลักษณะนี้ในลำดับพจนานุกรม

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

• กำหนดอาร์เรย์ที่เรียกว่า ret กำหนดตัวแปรประเภทจำนวนเต็ม n

• กำหนดวิธีการแก้ปัญหา () สิ่งนี้จะใช้ดัชนี รายการ และเคอร์เซอร์เป็นอินพุต

• ถ้า index =n ให้ใส่ curr เข้าไปที่ ret แล้ว return

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของรายการ[ดัชนี]

  • แก้การโทร (ดัชนี + 1, รายการ, สกุลเงิน + รายการ[ดัชนี, ผม])

• จากวิธีหลัก ให้ทำดังนี้

• สร้างรายการขนาด 100 ตั้งค่า n :=0, flag :=false

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

  • ถ้า s[i] เป็นลูกน้ำ ให้ข้ามไปที่การวนซ้ำถัดไป

  • มิฉะนั้นเมื่อ s[i] กำลังเปิดวงเล็บปีกกา ให้ตั้งค่าสถานะ :=true

  • มิฉะนั้นเมื่อ s[i] กำลังปิดวงเล็บปีกกา ให้ตั้งค่าสถานะ :=false และเพิ่ม n ขึ้น 1

  • ไม่เช่นนั้นให้เพิ่ม list[n] โดย s[i] ตอนนี้หากแฟล็กเป็นเท็จ ให้เพิ่ม n ขึ้น 1

• แก้การโทร(0, รายการ, สตริงว่าง)

• จัดเรียงอาร์เรย์ ret

• รีเทิร์น

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector <string> ret;
   int n;
   vector<string> expand(string s) {
      vector <string> list(100);
      n = 0;
      int flag = false;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == ','){
            continue;
         }else if(s[i] == '{'){
            flag = true;
         }else if(s[i] == '}'){
            flag = false;
            n++;
         }else{
            list[n] += s[i];
            if(!flag)n++;
         }
      }
      solve(0, list);
      sort(ret.begin(), ret.end());
      return ret;
   }
   void solve(int idx, vector <string> list, string curr = ""){
      if(idx == n){
         ret.push_back(curr);
         return;
      }
      for(int i = 0; i < list[idx].size(); i++){
         solve(idx + 1, list, curr + list[idx][i]);
      }
   }
};
main(){
   Solution ob;
   print_vector(ob.expand("{a,b}c{d,e}f"));
}

อินพุต

"{a,b}c{d,e}f"

ผลลัพธ์

[acdf, acef, bcdf, bcef, ]