Giả sử ta có chuỗi S đại diện cho danh sách các từ. Ở đây mỗi chữ cái trong từ có 1 hoặc nhiều lựa chọn. Nếu chỉ có một lựa chọn, chữ cái được biểu diễn như bình thường. Nếu có nhiều hơn một lựa chọn, dấu ngoặc nhọn bao quanh các lựa chọn. Ví dụ, "{a,b,c}" đại diện cho các lựa chọn ["a", "b", "c"]. Ví dụ, nếu đầu vào là "{a,b,c}d{e,f}", nó đại diện cho danh sách ["ade", "adf", "bde", "bdf", "cde", "cdf"].
Trả về tất cả các từ có thể hình thành theo cách này, theo thứ tự từ điển.
Để giải quyết, ta thực hiện các bước sau:
Định nghĩa mảng ret, định nghĩa biến nguyên n.
Định nghĩa phương thức solve(), nhận index, list và curr.
Nếu index = n, chèn curr vào ret và trả về.
Với i từ 0 đến kích thước list[index]:
Gọi solve(index + 1, list, curr + list[index, i]).
Từ phương thức main:
Tạo list kích thước 100, đặt n := 0, flag := false.
Với i từ 0 đến kích thước s - 1:
Nếu s[i] là dấu phẩy, bỏ qua vòng lặp hiện tại.
Ngược lại nếu s[i] là ngoặc mở, đặt flag := true.
Ngược lại nếu s[i] là ngoặc đóng, đặt flag := false và tăng n lên 1.
Ngược lại tăng list[n] thêm s[i], nếu flag là false thì tăng n lên 1.
Gọi solve(0, list, chuỗi rỗng).
Sắp xếp mảng ret.
Trả về ret.
Xem triển khai dưới đây để 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"Kết quả
[acdf, acef, bcdf, bcef, ]