LeetCode-1249. Minimum Remove to Make Valid Parentheses

LeetCode-1249. Minimum Remove to Make Valid Parentheses

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^5​​​​s[i]​​​ is one of​​'('​​​ ,​​')'​​​ and lowercase English letters​​.​​

​​题解：​​

​​找出需要删除的括号位置即可。​​

class Solution {public: string minRemoveToMakeValid(string s) { int n = s.length(); string res; stack st; unordered_set del; for (int i = 0; i < n; i++) { if (s[i] == '(') { st.push(i); } if (s[i] == ')') { if (st.empty() == false) { st.pop(); } else { del.insert(i); } } } while (st.empty() == false) { del.insert(st.top()); st.pop(); } for (int i = 0; i < n; i++) { if (del.find(i) != del.end()) { continue; } res += s[i]; } return res; }};

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