题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5831
给你一个只包含‘(’‘)’的字符串,然后让我们交换两个字符一次,问是否能得到一个合法的匹配;必须要交换一次,而且只能交换一次;
() No
))(( Yes这两个是比较特殊的注意一下;
可以把串中的第一个')'和最后一个'('交换一下,然后判断是否合法即可;
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<stack> using namespace std; #define INF 0xfffffff #define N 100050 typedef long long LL; int n; char s[N]; int Judge() { stack<char>sta; for(int i=0; i<n; i++) { if(s[i] == '(') sta.push(s[i]); else { if(!sta.empty()) sta.pop(); else return 0; } } if(!sta.empty()) return 0; return 1; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d", &n); scanf("%s", s); int Index1 = -1, Index2 = -1; for(int i=0; i<n; i++) { if(Index1 == -1 && s[i] == ')') Index1 = i; if(s[i]=='(') Index2 = i; } swap(s[Index1], s[Index2]); if(Judge()) puts("Yes"); else puts("No"); } return 0; }