企业官网建设流程全解析

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, 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©o)de)”
Output:“lee(t©o)de”
Explanation:“lee(t(co)de)” , “lee(t©ode)” would also be accepted.

Example 2:

Input:s = “a)b©d”
Output:“ab©d”

Example 3:

Input:s = “))((”
Output:“”
Explanation:An empty string is also valid.

Constraints:

• 1 < = s . l e n g t h < = 10 5 1 <= s.length <= 10^51<=s.length<=105
• s[i] is either ‘(’ , ‘)’, or lowercase English letter.

From: LeetCode
Link: 1249. Minimum Remove to Make Valid Parentheses

Solution:

Ideas:

use a stack to match ‘(’. Mark unmatched ‘)’ and leftover ‘(’ for removal, then build the answer.

Code:

#include<stdlib.h>#include<string.h>#include<stdbool.h>char*minRemoveToMakeValid(char*s){intn=strlen(s);int*stack=(int*)malloc(sizeof(int)*n);bool*remove=(bool*)calloc(n,sizeof(bool));inttop=0;for(inti=0;i<n;i++){if(s[i]=='('){stack[top++]=i;}elseif(s[i]==')'){if(top>0){top--;}else{remove[i]=true;}}}while(top>0){remove[stack[--top]]=true;}char*ans=(char*)malloc(n+1);intj=0;for(inti=0;i<n;i++){if(!remove[i]){ans[j++]=s[i];}}ans[j]='\0';free(stack);free(remove);returnans;}