資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究C++中的花括號展開
假設我們有一個字串S，它代表一個單詞列表。單詞中的每個字母都有一個或多個選項。如果只有一個選項，則字母按原樣表示。如果有多個選項，則用花括號分隔選項。例如，“{a,b,c}”將表示選項["a", "b", "c"]。現在，例如，如果輸入類似於"{a,b,c}d{e,f}"，這將表示列表["ade", "adf", "bde", "bdf", "cde", "cdf"]。
返回可以按這種方式形成的所有單詞，按字典順序排列。
為了解決這個問題，我們將遵循以下步驟：
定義一個名為ret的陣列，定義一個整型變數n
定義一個名為solve()的方法，它將index、list和curr作為輸入
如果index = n，則將curr插入ret並返回
對於範圍為0到list[index]大小的i
呼叫solve(index + 1, list, curr + list[index, i])
從主方法中，執行以下操作
建立一個大小為100的列表，設定n := 0，flag := false
對於範圍為0到s大小減1的i
如果s[i]是逗號，則跳到下一個迭代
否則，當s[i]是開括號時，設定flag := true
否則，當s[i]是閉括號時，設定flag := false並將n加1
否則，將list[n]增加s[i]，現在如果flag為false，則將n加1
呼叫solve(0, list, 空字串)
對ret陣列進行排序
返回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, ]
更新於：2020年4月30日
267 次瀏覽
廣告