단어 목록을 나타내는 문자열 S가 있다고 가정합니다. 여기에서 단어의 각 문자에는 1개 이상의 옵션이 있습니다. 옵션이 하나만 있는 경우 문자는 있는 그대로 표시됩니다. 둘 이상의 옵션이 있는 경우 중괄호로 옵션을 구분합니다. 예를 들어 "{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에서 목록[색인]의 크기까지의 i에 대해
-
solve(index + 1, list, curr + list[index, i])
호출
-
-
기본 방법에서 다음을 수행하십시오.
-
크기가 100인 목록을 만들고 n :=0으로 설정하고 플래그를 :=false로 설정
-
범위 0에서 s – 1까지의 i에 대해
-
s[i]가 쉼표이면 다음 반복으로 건너뜁니다.
-
그렇지 않으면 s[i]가 중괄호를 여는 경우 플래그 설정 :=true
-
그렇지 않으면 s[i]가 닫는 중괄호일 때 flag :=false를 설정하고 n을 1만큼 증가시킵니다.
-
그렇지 않으면 list[n]을 s[i]만큼 증가시키고 이제 flag가 false이면 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, ]