【Leetcode】【240406】1249. Minimum Remove to Make Valid Parentheses

本文主要是介绍【Leetcode】【240406】1249. Minimum Remove to Make Valid Parentheses，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

其实大部分是东京时间第二天凌晨才做的- -但国际服刷新比较晚
BGM：刀剑如梦

Decsripition

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

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.

Solution

Just use stack to pair left and right parentheses, but remeber to save the num-th of the remain char.

Code

class Solution {
public:string minRemoveToMakeValid(string s){typedef struct pair{char kyara;int num;};stack<pair>tree;bool judge[100005]={0};for(int i=0;i<s.length();++i){if(s[i]=='('){pair mid;mid.kyara=s[i];mid.num=i;tree.push(mid);}else if(s[i]==')'){if(!tree.empty()){pair mid=tree.top();if(mid.kyara=='(') tree.pop();else{pair curr;curr.kyara=s[i];curr.num=i;tree.push(curr);}}else{pair mid;mid.kyara=s[i];mid.num=i;tree.push(mid);}}}while(!tree.empty()){pair mid=tree.top();judge[mid.num]=1;tree.pop();}string c="";for(int i=0;i<s.length();++i){if(judge[i]==0) c.push_back(s[i]);}return c;}
};