当前位置:网站首页>LeetCode 1249. Minimum Remove to Make Valid Parentheses - FB高频题1
LeetCode 1249. Minimum Remove to Make Valid Parentheses - FB高频题1
2022-04-23 09:50:00 【CP Coding】
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, or
- It can be written as
AB
(A
concatenated withB
), whereA
andB
are valid strings, or - It can be written as
(A)
, whereA
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.
Constraints:
1 <= s.length <= 105
s[i]
is either'('
,')'
, or lowercase English letter.
题目说给定一个字符串包含英文字母和左右小括号'('和‘)’,字符串里的左右小括号有可能是不匹配的,要求移除最少个数的左右小括号使得剩下的是完全匹配的,返回移除后的有效字符串。
首先要搞清楚左右小括号的匹配原则,当遇到一个左括号时,后面必须要有一个右括号才能匹配,要是直到最后也没出现右括号则该左括号为无效需被删除;当遇到一个右括号时,其前面必须要有一个等着匹配的左括号,否则该右括号为无效需要被删除。
由此可见,整个删除过程是基于左括号的,因此可以用一个堆栈来记录待匹配的左括号,从头到尾扫一遍字符串,当遇到左括号就把左括号放入堆栈里(堆栈里放的是当前左括号的位置);当遇到右括号时,就判断此时堆栈是否为空,如不为空则从堆栈顶弹出一个左括号与其匹配,如为空表示该右括号需要被删除。按此方法直到遍历结束,结束后堆栈里剩下的左括号也都是要被删除的。在整个过程中用一个set来记录要被删除的括号的位置,最后再遍历一遍统一删除,这样效率会比较高。
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
rm = set()
st = []
for i,c in enumerate(s):
if c == '(':
st.append(i)
elif c == ')':
if not st:
rm.add(i)
else:
st.pop()
while st:
rm.add(st.pop())
res = []
for i,c in enumerate(s):
if i not in rm:
res.append(c)
return ''.join(res)
版权声明
本文为[CP Coding]所创,转载请带上原文链接,感谢
https://blog.csdn.net/hgq522/article/details/124333962
边栏推荐
- SAP 03-amdp CDs table function using 'with' clause
- Golang force buckle leetcode 396 Rotation function
- Two declaration methods of functions of JS
- Where is int a = 1 stored
- Nine abilities of agile manufacturing in the era of meta universe
- MySQL of database -- Fundamentals
- 计算机网络安全实验二|DNS协议漏洞利用实验
- Example of data object mask used by SAP translate
- Set the maximum width of the body, but why does the background color of the body cover the whole page?
- SAP pi / PO function operation status monitoring and inspection
猜你喜欢
云身份过于宽松,为攻击者打开了大门
工业元宇宙平台规划与建设
Planning and construction of industrial meta universe platform
Go language learning notes - slice, map | go language from scratch
防疫登记小程序
Enter "net start MySQL" and "system error 5. Access denied" appears. Detailed explanation of the problem
Leetcode题库78. 子集(递归 c实现)
Three challenges that a successful Devops leader should be aware of
Go language learning notes - language interface | go language from scratch
Set the maximum width of the body, but why does the background color of the body cover the whole page?
随机推荐
Planning and construction of industrial meta universe platform
ABAP CDs view with association example
Your guide to lowering your cholesterol with TLC (continuously updated)
从知识传播的维度对比分析元宇宙
golang力扣leetcode 396.旋转函数
重载、重写、隐藏的对比
自定义登录失败处理
Introduction to sap pi / PO login and basic functions
Cloud identity is too loose, opening the door for attackers
Cloud computing competition -- basic part of 2020 competition [task 3]
ABAP implementation publishes restful services for external invocation example
Using sqlmap injection to obtain the account and password of the website administrator
Pre parsing of JS
Simply understand = = and equals, why can string not use new
Code source daily question div1 (701-707)
Go language learning notes - array | go language from scratch
Redis 过期 key 清理删除策略汇总
最长公共前串
Kernel PWN learning (3) -- ret2user & kernel ROP & qwb2018 core
PHP笔记(一):开发环境配置