1249. Minimum Remove to Make Valid Parentheses

題目

給定一個string s，包含 (、)、及小寫字母

移除最小數量的括號使得所有括號是合法的( 每個左括號都能在右邊找到一個對應的右括號 )

合法的字串必須符合下面任何一條規則

• 空字串、或只包含小寫字母

• 可被寫成 AB (AB相鄰)，而A及B皆為合法字串

• 可被寫成 (A)，A為合法字串

條件

• 1 <= s.length <= $10^5$

• s[i] is either'(' , ')', or lowercase English letter.

思考test cases

Input: s = ""
Output: ""
Explanation: 空字串

Input: s = "))(("
Output: ""
Explanation: 全部移除後是空字串

Input: s = ")a)bcde(f("
Output: "abcdef"
Explanation: 括號全部移除

Input: s = "(((a(b)(c)(d)e)))"
Output: "(((a(b)(c)(d)e)))"
Explanation: 全部不移除

Input: s = "((((((a)(((((("
Output: "(a)"
Explanation: 只有一組匹配

Input: s = "))))))(a)))))"
Output: "(a)"
Explanation: 只有一組匹配

解題思路

1. 實際上只需要處理括號的匹配，由於可將由括號不斷與前面出現的左括號抵銷，可使用stack來保留狀態，當可以組成一對就移除

2. stack為空時右括號一律是非法的

3. 字串處理完之後還留在stack中的都是匹配不到右括號的左括號

4. 由於需要保留字母，需要額外儲存每個括號的所在位置

Coding思路

1. 遍歷字串，並用另一個stack紀錄要移除的括號位置

   1. 若為字母則跳過

   2. 若為左括號，則將index push到stack

   3. 若為右括號

      1. stack為空，紀錄括號位置

      2. 反之則pop掉stack頂端

2. 處理stack剩餘內容

   1. 若兩個stack皆為空，則傳入字串值為答案

3. 倒過來遍歷字串組成答案

   1. 若為字母則append到末端

   2. 若該index為需要移除的則跳過

   3. 都不是則append到末端

Solution

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        const int n = s.size();
        stack<int> st;
        stack<int> shouldRemoved;

        for (int i = 0; i < n; i += 1) {
            if (s[i] == '(') {
                st.push(i);
            } else if (s[i] == ')') {
                if (st.empty()) {
                    shouldRemoved.push(i);
                } else {
                    st.pop();
                }
            }
        }

        if (st.empty() && shouldRemoved.empty()) {
            return s;
        }

        string ans = "";
        for (int i = n - 1; i >= 0; i -= 1) {
            if (!st.empty() && i == st.top()) {
                st.pop();
                continue;
            }
            if (!shouldRemoved.empty() && i == shouldRemoved.top()) {
                shouldRemoved.pop();
                continue;
            }
            ans += s[i];
        }
        return string(ans.rbegin(), ans.rend());
    }
};

Time Complexity: O(N)

Space Complexity: O(N)

Should be Optmized

• 用iterator減少copy的次數

• 透過inplace的方法空間複雜度達到 O(1)

  • 範例