数据结构
网络
关系数据库管理系统 (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 次浏览
广告