昆明市网站建设_网站建设公司_建站流程_seo优化

题目描述

给你一个由'('、')'和小写字母组成的字符串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 <= 105
• s[i]可能是'('、')'或英文小写字母

题解

力扣原题链接

这道题已经多次反馈考过，并且栈还是比较高频的题目，建议一定要掌握。

思路：栈模拟

1. 保证结果中的括号全部有效的要求就是保证所有右括号都有对应的左括号对应(左括号数量 = 右括号数量)，并且在字符串任意前缀，右括号不能多余左括号数量。
2. 基于1的直接使用栈进行模拟，定义leftCount = 0记录前缀中已经包含的左括号数量，循环遍历输入字符串吧先保证在字符串任意前缀，右括号不能多余左括号数量，具体逻辑，对于字符c：
   • 属于小写字母,直接压入栈。
   • 属于(,直接压入栈，并更新leftCount += 1
   • 属于),此时需要判断左侧是有未匹配括号,如果leftCount ==0,直接跳过不压入栈。否则将当前）压入栈，并更新leftCount -=1
3. 根据2的逻辑处理之后，可以保证在字符串任意前缀，右括号不能多余左括号数量,但并不能保证栈中左括号 = 右括号数量，此时左括号数量可能多余右括号数量，多个个数就是leftCount, 至于移除多个数量只需要弹栈的过程中，如果c == '(' 并且 leftCount >0，直接丢弃并更新leftCount -= 1就行。最后得到的字符串就是结果。
4. 上面算法逻辑的实现复杂度为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)}