LeetCode Weekly Contest 142 : 1096. Brace Expansion II

なんだこれ…。
https://leetcode.com/contest/weekly-contest-142/problems/brace-expansion-ii/

問題

文字列の集合を表す記法がある。
この記法における表現、集合Rは以下のように定義される。

• sがアルファベット1文字のときそれは有効な表現で、R(s)はsだけからなる集合
• a,bが有効な表現の場合、R(ab) := R(a)とR(b)の直積
• a,b,c...が有効な表現の場合、R("{a,b,...}") := R(a)、R(b)…の和集合

有効な表現sが与えられたとき、R(s)を求めよ。

解法

愚直に再帰的に構文解析していくだけ。
直積の場合演算子が入らないのでちょっと面倒。

class Solution {
public:
	string A;
    set<string> hoge(int L,int R){
		//cout<<L<<" "<<R<<" "<<A.substr(L,R-L)<<endl;
		set<string> S;
		if(L>=R) return S;
		int i;
		if(A[L]=='{') {
			int num=1;
			int pre=L;
			for(i=L+1;i<=R;i++) {
				if(A[i]=='{') num++;
				if(A[i]=='}') num--;
				
				if(num==1 && A[i]==',') {
					auto t=hoge(pre+1,i);
					FORR(v,t) S.insert(v);
					pre=i;
				}
				if(num==0) {
					auto t=hoge(pre+1,i);
					FORR(v,t) S.insert(v);
					break;
				}
			}
			//cout<<"!"<<i<<" "<<R<<endl;
			if(i+1==R) return S;
			auto T=hoge(i+1,R);
			set<string> V;
			FORR(s,S) FORR(t,T) V.insert(s+t);
			return V;
		}
		else {
			S.insert(string(1,A[L]));
			if(L+1==R) return S;
			auto T=hoge(L+1,R);
			set<string> V;
			FORR(s,S) FORR(t,T) V.insert(s+t);
			return V;
		}
		
		
		
		
	}
    vector<string> braceExpansionII(string expression) {
		int i;
		A.clear();
		A="{"+expression+"}";
		auto v=hoge(0,A.size());
		vector<string> S;
		FORR(s,v) S.push_back(s);
		return S;
        
    }
};

まとめ

パズル的な面白さより、実装力を見るサイトだとするならしょうがないかね…。