1249. Minimum Remove to Make Valid Parentheses

發表於 | 分類於

problem

solution

  1. 遍歷字串，遇到字母加進字串ret，遇到左括號push stack，遇到右括號且如果stack為空，則不加入字串ret，代表目前為止右括號出現次數多餘左括號，遇到右括號且stack 不為空則加入字串ret並pop stack。

  2. 最後檢查是否有左括號在字串ret後方且沒有對應的右括號，並將他移除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<char> sta;
        string ret;
        for(char c:s){
            if(c>='a' && c<='z') ret+=c;
            else if(c=='(') {
                sta.push(c);
                ret+=c;
            }
            else{
                // )
                if(sta.empty()) continue;
                else{
                    sta.pop();
                    ret+=c;
                }        
            }
        }
        // "())()((("
        // 從後面移除多餘的左括號
        string ans;
        int n= ret.size();
        for(int i=n-1;i>-1;i--){
            if(ret[i]=='(' && !sta.empty()){
                sta.pop();
                continue;
            }
            ans+=ret[i];
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n)