Leetcode 1249:移除无效的括号(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1249:移除无效的括号(超详细的解法!!!)

in leetcode with 0 comment

给你一个由 '('')' 和小写字母组成的字符串 s

你需要从字符串中删除最少数目的 '(' 或者 ')' (可以删除任意位置的括号),使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下 任意一条 要求:

示例 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)" 

提示:

解题思路

一个简单的思路就是先遍历一遍,通过栈找出无效的括号位置,具体操作如下:如果碰到')',判断栈顶元素是不是'(',如果是的话,将栈顶元素弹出(匹配成功);如果不是,将此时')'及其位置加入到栈中(无效括号)。如果碰到'(',直接将该元素和位置同时加入到栈中即可。

然后再遍历一遍字符串,判断字符串的位置是不是出现在栈中,如果在栈中,那么就不添加到最后的结果中,否则添加进去即可。

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        st = []
        for i, v in enumerate(s):
            if v == ')':
                if st and st[-1][0] == '(':
                    st.pop()
                    continue
                st.append([v, i])
            elif v == '(':
                st.append([v, i])
        
        res, t = "", 0
        for i, v in enumerate(s):
            if t < len(st) and i == st[t][1]:
                t += 1
                continue
            res += v
        return res

或者第二次遍历的时候直接遍历栈,因为栈中存放了位置信息,那么我们可以将两个栈中元素之间的字符串添加到结果中去。

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        st = []
        for i, v in enumerate(s):
            if v == ')':
                if st and st[-1][0] == '(':
                    st.pop()
                    continue
                st.append([v, i])
            elif v == '(':
                st.append([v, i])
        
        res, pre = "", 0
        for v, i in st:
            res += s[pre:i]
            pre = i + 1
        else:
            res += s[pre:]
        return res

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses