yoruru的努力日記

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(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.

Constraints:

• 1 <= s.length <= 105
• s[i] is either'(' , ')', or lowercase English letter.

SOL：

這一題的解題思路是，創造一個int stack來放未被配對的左括號 '(' 的index。當遇到右括號 ')'時，若stack為空，則代表當前沒有需要右括號，此右括號會是多餘的，可以直接把這個右括號以空格 ' ' 取代；否則pop一個左括號index表示配對完成左右括號。

當拜訪完一次s時，若stack不為空，則代表還有無法被配對的左括號 '('，因此直接把s在那些位置的值也設為空格 ' '。

最後對於字串s，再將空格 ' ' 全部拿掉即是答案。因為C語言並沒有內建的strtrim函數，所以簡單用個char stack來接非空格的字元。

參考影片：【每日一题】1249. Minimum Remove to Make Valid Parentheses, 8/14/2020

char * minRemoveToMakeValid(char * s){
    int len = strlen(s);
    int *stack = (int *)malloc(sizeof(int)*len);
    int top = -1;
    for(int i = 0; i < len; i++){
        if(s[i]=='('){
            stack[++top] = i;
        }
        else if(s[i]==')'){
            if(top==-1) //empty stack
                s[i]=' ';
            else
                top--;
        }
    }
    while(top>-1){
        s[stack[top--]]=' ';
    }
    char *result = (char *)malloc(sizeof(char)*(len+1));
    top = -1;
    for(int i = 0; i < len; i++){
        if(!isspace(s[i]))
            result[++top]=s[i];
    }
    result[++top]='\0';
    free(stack);
    return result;
}