[leetcode] 1249. Minimum Remove to Make Valid Parentheses

[leetcode] 1249. Minimum Remove to Make Valid Parentheses

Description

Given a string s of ‘(’ , ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(’ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, orIt can be written as AB (A concatenated with B), where A and B are valid strings, orIt can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)"Output: "lee(t(c)o)de"Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"Output: "ab(c)d"

Example 3:

Input: s = "))(("Output: ""Explanation: An empty string is also valid.

Example 4:

Input: s = "(a(b(c)d)"Output: "a(b(c)d)"

Constraints:

1 <= s.length <= 10^5s[i] is one of ‘(’ , ‘)’ and lowercase English letters.

分析

题目的意思是：去除字符串中不合法的括号，是的剩下的字符串中括号是合法的。求最小的去除个数。这里思路很直接，需要用到栈，我用了两个栈，其中一个栈存放括号，匹配就出栈，不匹配就入栈，第二个栈存放的是栈中括号的索引。我看了一下别人的解法，好像可以直接把字符串某位置的括号置空，这样的话就不需要像我用两个栈来模拟了，哈哈哈。

代码

class Solution: def minRemoveToMakeValid(self, s: str) -> str: stack1=[] stack2=[] n=len(s) for i in range(n): if(s[i]=='('): stack1.append(s[i]) stack2.append(i) if(s[i]==')'): if(stack1 and stack1[-1]=='('): stack1.pop() stack2.pop() else: stack1.append(s[i]) stack2.append(i) res='' for i in range(n): if(i not in stack2): res+=s[i] return res

参考文献

​​[LeetCode] Super simple Python solution with explanation. Faster than 100%, Memory Usage less than 100%​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。