LeetCode-1249.移除无效的括号
题目下图所示：
题目大概的意思是输入一组字符串，字符串包含小写字母和‘(’、‘)’，保留能匹配成一对的小括号，去掉多余的‘(’或者‘)’。答案可能会有多个，只需要输出一个正常的字符串就可以。
方案：
括号匹配，我们可以使用栈的数据结构来匹配成对的括号，遇到一个左括号‘(’就入栈，如果遇到一个右括号‘)’，需要判断栈是否为空(代表右括号前面是否有左括号跟它匹配)，栈为空，那么这个就是无效的右括号；如果遍历完字符串，栈不为空，还有左括号‘(’，那么这些左括号也是无效的。
主要步骤如下图所示：
图1为原始的数组；C代表当前遍历到的字符位置；S代表栈，存储的是左括号的位置，为了找到右括号匹配之后复原左括号的，如果没有匹配到就是无效字符。
图2为遍历到一个左括号，先将左括号设置为‘.’，将位置编号入栈。
图3跟图2描述一致。
图4为遍历到一个右括号，先判断S栈是否为空，S栈不空，将栈顶的对应位置的字符设置回左括号，然后位置序号出栈。
图5跟图4描述一致。
图6为遍历到一个右括号，但是S栈为空，所有当前的右括号为无效字符，设置为‘.’。
图7为遍历完整的字符，去除.的无效字符，最后就是有效的字符串。
实现代码
class Solution {public:string minRemoveToMakeValid(string s) {string res;int nLen = s.length();stack<int> p;for(int i=0; i<nLen; i++) {//判断左括号入栈//可能没有右括号匹配，暂设置为.if(s[i] == '(') {p.push(i);s[i] = '.';}//判断是右括号并且栈不为空(代表前面有左括号)，可以做匹配，出栈//恢复前面的左括号else if(s[i] == ')' && !p.empty()) {s[p.top()] = '(';p.pop();}//没有左括号匹配，将当前符号复制为.else if(s[i] == ')' && p.empty()) {s[i] = '.';}}//当不是.，代表是有效符号for(int i=0; i<nLen; i++) {if(s[i] != '.') {res += s[i];}}return res;}};
喜欢的可以关注公众号查看更多的文章