LeetCode 921 Minimum Add to Make Parentheses Valid

LeetCode

A parentheses string is valid if and only if:

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

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. For example, if s = "()))", you can insert an opening parenthesis to be "(**(**)))" or a closing parenthesis to be "())**)**)".

Return the minimum number of moves required to make s valid.

Example 1:

Input: s = “())”
Output: 1

Example 2:

Input: s = “(((“
Output: 3

Constraints:

1 <= s.length <= 1000 s[i] is either '(' or ')'.

题目大意：

最小加括号数使得配对

Stack解题思路(推荐)：

跟Leetcode 1249一样。括号题优先考虑用Stack。此题将下标存于stack中，stack留下的是不合法括号下标，也就是需要删除的

LeetCode 1249 Minimum Remove to Make Valid Parentheses 求一个最优解 Medium, Stack
LeetCode 921 Minimum Add to Make Parentheses Valid 求一个最优解 Medium, Stack
LeetCode 301 Remove Invalid Parentheses 求所有最优解 Hard，此题 答案包含上题, BFS

解题步骤：

注意事项：

1. Python代码：

   def minAddToMakeValid(self, s: str) -> int:
   	stack, res = [], ''
   	for i in range(len(s)):
   		if s[i] == '(':
   			stack.append(i)
   		elif stack and s[stack[-1]] == '(' and s[i] == ')':  # remember
   			stack.pop()
   		elif s[i] == ')':
   			stack.append(i)
   	return len(stack)

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

---

统计算法II解题思路：

类似于Leetcode 032 Longest Valid Parentheses的统计算法。用这两种情况来写即可： ()), )(. 若左括号数left出现负数，根据第一个规律，重设left，计入res

Python代码：

def minAddToMakeValid2(self, s: str) -> int:
	left, res = 0, 0
	for char in s:
		if char == '(':
			left += 1
		else:
			left -= 1
			if left < 0:
				res += 1
				left = 0
	return res + abs(left)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)