可以把a看成左括号,b看成右括号,这样判断是否为好串就能转化成括号匹配问题
方法一:开栈。碰到左括号就入栈,右括号就出栈,使左右括号对应匹配,若有一次栈空(即左括号不够)但还有右括号,则右括号多了,不是好串。最终只要栈空,就是好串,否则不是好串
方法二:计数。本题中只有一种括号,因此无需开栈,只需要记录当前的左右括号出现次数。具体说来,出现左括号时cnt++,出现右括号cnt--,如果cnt<0即不够减了,就不是好串。最终若cnt==0,就是好串,否则不是好串。
#include <bits/stdc++.h> using namespace std; int main(){ string s; cin >> s; int len = s.length(); long long cnt =0; for(int i=0;i<len;i++){ if(s[i]=='a') cnt++; if(s[i]=='b') cnt--; if(cnt<0){ cout << "Bad\n"; return 0; } } if(cnt==0) cout << "Good\n"; else cout << "Bad\n"; return 0; }
当然,如果题目给了abcdefg,也就是说左右括号不止一种,那就只能用栈了