网络异常，图片无法展示
|
给你一个由 '('、')' 和小写字母组成的字符串 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 = "))((" 输出： "" 解释： 空字符串也是有效的 复制代码
示例 4：
输入： s = "(a(b(c)d)" 输出： "a(b(c)d)" 复制代码
提示：
1 <= s.length <= 10^5s[i]可能是'('、')'或英文小写字母
本题要求将输入字符串中无效的括号删除
涉及到括号匹配的问题，都可以借助栈来解题
因为栈的性质为先进后出，所以当用栈来维护左括号的时候，遇到右括号的时候，如果栈不为空，则栈顶元素就是当前右括号对应的左括号
本题同样利用该技巧，在遍历输入字符串的过程中，如果当前字符为左括号，将对应下标压入栈中
如果当前字符为右括号，判断栈是否为空
如果栈不为空，则栈顶元素为当前右括号对应的左括号，将栈顶元素弹出，继续遍历
如果栈为空，则说明当前右括号没有与之匹配的左括号，则该右括号为无效括号，将其从输入字符串中删除
如果当前字符为小写字符，无需任何操作，继续遍历
这样当遍历完输入字符串，就删除了所有无效右括号，此时如果栈不为空，则栈中保存到就是所有无效左括号的下标
将栈顶元素弹出，并将输入字符串中对应字符删除，直到栈为空
最后返回处理后的输入字符串即可
过程演示如下：
网络异常，图片无法展示
|
代码如下：
var minRemoveToMakeValid = function(s) { // 初始化栈，存储左括号下标 const stack = []; // 遍历输入字符串 for(let i = 0;i<s.length;i++){ // 如果是左括号，将下标入栈 if(s[i]==='('){ stack.push(i) }else if(s[i]===')'){ // 如果是右括号 // 如果栈不为空，说明栈顶左括号为该右括号对应左括号，将栈顶元素弹出 if(stack.length) stack.pop(); // 如果栈为空，说明当前右括号为多余右括号，将其删除 else{ s = s.substring(0,i)+s.substring(i+1); i--; } } } // 遍历完后，如果栈不为空，说明栈中为多余左括号的下标，将对应字符删除 while(stack.length){ const ind = stack.pop(); s = s.substring(0,ind)+s.substring(ind+1) } // 返回处理后的字符串 return s; }; 复制代码
至此我们就完成了 leetcode-1249-移除无效的括号
如有任何问题或建议，欢迎留言讨论！
