华为OD面试手撕真题 - 移除无效括号
题目描述
给你一个由'('、')'和小写字母组成的字符串s。
你需要从字符串中删除最少数目的'('或者')'（可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下任意一条要求：
- 空字符串或只包含小写字母的字符串
- 可以被写作
AB（A连接B）的字符串，其中A和B都是有效「括号字符串」 - 可以被写作
(A)的字符串，其中A是一个有效的「括号字符串」
示例1
输入：s = "lee(t(c)o)de)" 输出："lee(t(c)o)de" 解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。示例2
输入：s = "a)b(c)d" 输出："ab(c)d"示例3
输入：s = "))((" 输出："" 解释：空字符串也是有效的提示
1 <= s.length <= 105s[i]可能是'('、')'或英文小写字母
题解
力扣原题链接
这道题已经多次反馈考过，并且栈还是比较高频的题目，建议一定要掌握。
思路：栈模拟
- 保证结果中的括号全部有效的要求就是
保证所有右括号都有对应的左括号对应(左括号数量 = 右括号数量)，并且在字符串任意前缀，右括号不能多余左括号数量。 - 基于1的直接使用栈进行模拟，定义
leftCount = 0记录前缀中已经包含的左括号数量，循环遍历输入字符串吧先保证在字符串任意前缀，右括号不能多余左括号数量，具体逻辑，对于字符c：- 属于小写字母,直接压入栈。
- 属于
(,直接压入栈，并更新leftCount += 1 - 属于
),此时需要判断左侧是有未匹配括号,如果leftCount ==0,直接跳过不压入栈。否则将当前）压入栈，并更新leftCount -=1
- 根据2的逻辑处理之后，可以保证
在字符串任意前缀，右括号不能多余左括号数量,但并不能保证栈中左括号 = 右括号数量，此时左括号数量可能多余右括号数量，多个个数就是leftCount, 至于移除多个数量只需要弹栈的过程中，如果c == '(' 并且 leftCount >0，直接丢弃并更新leftCount -= 1就行。最后得到的字符串就是结果。 - 上面算法逻辑的实现复杂度为O(n)
c++
class Solution { public: string minRemoveToMakeValid(string str) { // 栈模拟 stack<char> s; int n = str.size(); // 前面剩余未匹配左括号的数量 int leftCount = 0; for (int i = 0; i < n; i++) { char c = str[i]; if (c == '(') { leftCount++; s.push(c); } else if (c == ')') { // 前面未匹配左括号数量 <= 0， 当前右括号不合法 if (leftCount <= 0) { continue; } // 匹配一个左 leftCount--; s.push(c); } else { s.push(c); } } string res = ""; // 收尾操作，主要是移除未匹配的左括号 while (!s.empty()) { char c = s.top(); s.pop(); // 非法的左括号，移除 if (c == '(' && leftCount > 0) { leftCount--; continue; } res.push_back(c); } // 反向 reverse(res.begin(), res.end()); return res; ; } };JAVA
import java.util.*; class Solution { public String minRemoveToMakeValid(String str) { // 栈模拟 Deque<Character> stack = new ArrayDeque<>(); int n = str.length(); // 前面剩余未匹配左括号的数量 int leftCount = 0; for (int i = 0; i < n; i++) { char c = str.charAt(i); if (c == '(') { leftCount++; stack.push(c); } else if (c == ')') { // 前面未匹配左括号数量 <= 0，当前右括号不合法 if (leftCount <= 0) { continue; } // 匹配一个左括号 leftCount--; stack.push(c); } else { stack.push(c); } } StringBuilder res = new StringBuilder(); // 收尾操作，主要是移除未匹配的左括号 while (!stack.isEmpty()) { char c = stack.pop(); // 非法的左括号，移除 if (c == '(' && leftCount > 0) { leftCount--; continue; } res.append(c); } // 反向 return res.reverse().toString(); } }Python
classSolution:defminRemoveToMakeValid(self,s:str)->str:# 栈模拟stack=[]# 前面剩余未匹配左括号的数量leftCount=0forcins:ifc=='(':leftCount+=1stack.append(c)elifc==')':# 前面未匹配左括号数量 <= 0，当前右括号不合法ifleftCount<=0:continue# 匹配一个左括号leftCount-=1stack.append(c)else:stack.append(c)res=[]# 收尾操作，主要是移除未匹配的左括号whilestack:c=stack.pop()# 非法的左括号，移除ifc=='('andleftCount>0:leftCount-=1continueres.append(c)# 反向return''.join(reversed(res))JavaScript
/** * @param {string} s * @return {string} */varminRemoveToMakeValid=function(s){// 栈模拟conststack=[];// 前面剩余未匹配左括号的数量letleftCount=0;for(constcofs){if(c==='('){leftCount++;stack.push(c);}elseif(c===')'){// 前面未匹配左括号数量 <= 0，当前右括号不合法if(leftCount<=0){continue;}// 匹配一个左括号leftCount--;stack.push(c);}else{stack.push(c);}}constres=[];// 收尾操作，主要是移除未匹配的左括号while(stack.length>0){constc=stack.pop();// 非法的左括号，移除if(c==='('&&leftCount>0){leftCount--;continue;}res.push(c);}// 反向returnres.reverse().join('');};Go
funcminRemoveToMakeValid(sstring)string{// 栈模拟stack:=make([]rune,0)// 前面剩余未匹配左括号的数量leftCount:=0for_,c:=ranges{ifc=='('{leftCount++stack=append(stack,c)}elseifc==')'{// 前面未匹配左括号数量 <= 0，当前右括号不合法ifleftCount<=0{continue}// 匹配一个左括号leftCount--stack=append(stack,c)}else{stack=append(stack,c)}}res:=make([]rune,0)// 收尾操作，主要是移除未匹配的左括号forlen(stack)>0{c:=stack[len(stack)-1]stack=stack[:len(stack)-1]// 非法的左括号，移除ifc=='('&&leftCount>0{leftCount--continue}res=append(res,c)}// 反向fori,j:=0,len(res)-1;i<j;i,j=i+1,j-1{res[i],res[j]=res[j],res[i]}returnstring(res)}