8ms solution. Count the open and close parentheses and do DFS.


  • 0

    At the first glance, this is a really hard problem. Because the combination would blow up the memory if the input string is long enough. And it makes to think in DP direction......
    Once I checked the tag, I got the following solution. However, this is not the first version. The first solution is using unordered_set<string> to filter out the duplicates. But, you may find that the duplicates are because the same char could be put at the same position. So a simple check would bypass this issue. The runtime is improved from 90ms(unordered_set) to 8ms (vector<string>).

    class Solution {
    public:
        vector<string> removeInvalidParentheses(string s) {
            int l=0, r=0, maxlen=0;
            vector<string> res;
            string t;
            build(0, res, t, s, l, r, maxlen);
            return res;
        }
        void build(int start, vector<string>& res, string& t, string& s, int l, int r, int& maxlen){
            //  if open is less than close, then it's not a candidate
            if(l<r) return;
            if(l==r){
                int tlen=t.length();
                if(tlen>=maxlen){
                    if(tlen>maxlen) res.clear();
                    maxlen=tlen;
                    res.push_back(t);
                }
            }
            char pre=0;
            for(int i=start; i<s.length()&&t.length()+s.length()-i>=maxlen; ++i){
                char c=s[i];
                // if the current char is same as previous, then it is a duplicate. Skip it.
                if(pre!=c){
                    t.push_back(c);
                    int tl=c=='('?l+1:l;
                    int tr=c==')'?r+1:r;
                    build(i+1, res, t, s, tl, tr, maxlen);
                    t.pop_back();
                }
                pre=c;
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.