Leetcode 1249 - Minimum Remove to Make Valid Parentheses

題目

Problem#

題目給你一個字串，其中包含了 ( 和 )，問你刪除不定數量的括弧後使得括弧平衡(每個 ( 都有其對應的 ))，字串長怎樣。

想法#

先掃一遍，用 stack 匹配括弧，遇到 ( push、遇到 ) pop (如果不是空)，最後 stack 剩下的會是沒匹配到的

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

Copy

#define N 100000
 
class Solution
{
public:
    string minRemoveToMakeValid(string s)
    {
        bool vis[N+5];
        vector<int> stk;
        string ans;
        
        memset(vis, true, sizeof(vis));
        
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == '(')
                stk.push_back(i);
            else if(s[i] == ')')
            {
                if(!stk.empty())
                    stk.pop_back();
                else
                    vis[i] = false;
            }
        }
 
        for(int i : stk)
            vis[i] = false;
 
        for(int i = 0; i < s.size(); i++)
        {
            if(vis[i]) ans += s[i];
        }
        
        return ans;
    }
};

view raw leetcode/1249.cpp delivered with ❤ by emgithub

賞析#

• 其實我們並不在乎左括弧的位置，只在乎數量，那 stack 大可以退化成一個 counter，然後 vis 可以用不再字串輸入集合裡的文字取代，這樣就優化掉了
  • 掃兩次，一次消除 ( 另一次消除 )
  • https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/discuss/1073189/C%2B%2B-or-2-Approaches-or-O(n)-Beats-100-or-No-Extra-Space-(Best)-or-Explanation