[leetcode] 1541. Minimum Insertions to Balance a Parentheses String

[leetcode] 1541. Minimum Insertions to Balance a Parentheses string

Description

Given a parentheses string s containing only the characters ‘(’ and ‘)’. A parentheses string is balanced if:

Any left parenthesis ‘(’ must have a corresponding two consecutive right parenthesis ‘))’.Left parenthesis ‘(’ must go before the corresponding two consecutive right parenthesis ‘))’.

In other words, we treat ‘(’ as openning parenthesis and ‘))’ as closing parenthesis.

For example, “())”, “())(())))” and “(())())))” are balanced, “)()”, “()))” and “(()))” are not balanced.

You can insert the characters ‘(’ and ‘)’ at any position of the string to balance it if needed.

Return the minimum number of insertions needed to make s balanced.

Example 1:

Input: s = "(()))"Output: 1Explanation: The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be "(())))" which is balanced.

Example 2:

Input: s = "())"Output: 0Explanation: The string is already balanced.

Example 3:

Input: s = "))())("Output: 3Explanation: Add '(' to match the first '))', Add '))' to match the last '('.

Example 4:

Input: s = "(((((("Output: 12Explanation: Add 12 ')' to balance the string.

Example 5:

Input: s = ")))))))"Output: 5Explanation: Add 4 '(' at the beginning of the string and one ')' at the end. The string becomes "(((())))))))".

Constraints:

1 <= s.length <= 10^5s consists of ‘(’ and ‘)’ only.

分析

题目的意思是：给定括号序列，一个左括号匹配两个右括号。然后求最小的插入括号序列是的括号序列合法。这道题我参考了一下别人的实现，主要是用到栈的思想，左括号入栈，遇见右括号出栈，这时出栈的时候要计算是否合法，当当前的下一个位置还是右括号，说明合法；如果当前的下一个位置为其他的，则res+=1；最后当栈不为空需要出栈一个，否则左括号不匹配，res+=1；最后一种情况是右括号遍历到末尾了，这时候res+=1，直接跳出循环就行了。

情况有点多，所以出现bug的几率就变大了，哈哈哈。

代码

class Solution: def minInsertions(self, s: str) -> int: s1=[] i=0 n=len(s) res=0 while(i

参考文献

​​[LeetCode] Leetcode 5470：平衡括号字符串的最少插入次数​​

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