1261 String Popping

source.cpp

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <sstream>
#include <cstring>
#include<map>
using namespace std;
map<string, int>mp;
int solve(string s) {
	if (s == "")
		return 1;
	if (mp.count(s))
		return mp[s];
	int i, j;
	int ret = false;
	for ( i = 0; i < s.size(); ++i) {
		for (j = i; j < s.size(); ++j)
			if (s[i] != s[j])break;
		if (j >= i + 2) {
			string sub = s.substr(0, i) + s.substr(j);
			ret = ret | solve(sub);
			i = j-1;
		}
	}
	return mp[s]=ret;
}
int main(){
	int t;
	cin >> t;
	string s;
	while (t--) {
		cin >> s;
		cout << solve(s) << endl;;

	}
	system("pause");
	return 0;
}