Mở rộng Brace trong C ++

Giả sử chúng ta có một chuỗi S đại diện cho một danh sách các từ. Ở đây mỗi chữ cái trong từ có 1 hoặc nhiều tùy chọn. Nếu chỉ có một lựa chọn, chữ cái được biểu diễn như hiện tại. Nếu có nhiều hơn một tùy chọn, thì dấu ngoặc nhọn sẽ phân tách các tùy chọn. Vì vậy, ví dụ, "{a, b, c}" sẽ đại diện cho các tùy chọn ["a", "b", "c"]. Ví dụ:nếu đầu vào là "{a, b, c} d {e, f}" thì điều này sẽ đại diện cho danh sách ["ade", "adf", "bde", "bdf", "cde", "cdf"].

Trả lại tất cả các từ có thể được tạo theo cách này, theo thứ tự từ vựng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng được gọi là ret, xác định một biến kiểu số nguyên n

• xác định một phương thức giải quyết (), điều này sẽ lấy chỉ mục, danh sách và curr làm đầu vào

• nếu index =n, sau đó chèn curr vào ret và trả về

• cho tôi trong phạm vi từ 0 đến kích thước của danh sách [chỉ mục]

  • gọi giải quyết (chỉ mục + 1, danh sách, curr + danh sách [chỉ mục, i])

• Từ phương thức chính, hãy thực hiện như sau

• tạo một danh sách có kích thước 100, đặt n:=0, flag:=false

• cho tôi trong phạm vi từ 0 đến kích thước của s-1

  • nếu s [i] là dấu phẩy thì chuyển sang lần lặp tiếp theo

  • ngược lại khi s [i] đang mở dấu ngoặc nhọn thì hãy đặt cờ:=true

  • ngược lại khi s [i] đang đóng dấu ngoặc nhọn, thì hãy đặt cờ:=false và tăng n lên 1

  • nếu không, hãy tăng danh sách [n] lên s [i], bây giờ nếu cờ là false, hãy tăng n lên 1

• gọi giải quyết (0, danh sách, chuỗi trống)

• sắp xếp mảng ret

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

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

Đầu ra

[acdf, acef, bcdf, bcef, ]