LeetCode 1249 Minimum Remove to Make Valid Parentheses

LeetCode

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 with B), where A and B are valid strings, or
It 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<sup>5</sup>
* s[i] is either'(' , ')', or lowercase English letter.

题目大意：

去掉最小不合法括号数剩下的字符串。

Stack算法思路：

括号题优先考虑用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. 当括号配对时才出栈 Line 6

Python代码：

def minRemoveToMakeValid(self, s: str) -> str:
	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)
	for i in range(len(s)):
		if i in set(stack):
			continue
		res += s[i]
	return res

算法分析：

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