My 0ms C++ solution, improved depth-limited-DFS, beat 91.01%


  • 1
    M
    class Solution {
    private:
    	vector<string> ans;
    	vector<int> delLeft;
    	void getAns(string& s, string cur, int pos, int cntl, int cntr, int cnt) {
    		if (!(cntl || cntr)) ans.push_back(cur + s.substr(pos));
    		else {
    			for (int tail = s.length() - cntl - cntr;pos <= tail;++pos) {
    				if (s[pos] == ')') {
    					if (cntr && (cur.empty() || cur.back() != ')'))
    						getAns(s, cur, pos + 1, cntl, cntr - 1, cnt);
    					if (cnt == 0) return;
    					--cnt;
    					cur += ')';
    				}
    				else if (s[pos] == '(') {
    					if (cntr == 0 && cntl > delLeft[pos] && (cur.empty() || cur.back() != '('))
    						getAns(s, cur, pos + 1, cntl - 1, cntr, cnt);
    					++cnt;
    					cur += '(';
    				}
    				else cur += s[pos];
    			}
    		}
    	}
    public:
    	vector<string> removeInvalidParentheses(string s) {
    		if (s == "") return vector<string> (1, "");
    		int cntr = 0;
    		delLeft.resize(s.length());
    		delLeft[s.length() - 1] = 0;
    		for (int i = s.length() - 1;i > 0;--i) {
    			if (s[i] == ')') ++cntr, delLeft[i - 1] = delLeft[i];
    			else if (s[i] == '(') {
    				if (cntr) --cntr, delLeft[i - 1] = delLeft[i];
    				else delLeft[i - 1] = delLeft[i] + 1;
    			}
    			else delLeft[i - 1] = delLeft[i];
    		}
    		ans.resize(0);
    		if (s[0] == '('&&cntr == 0) getAns(s, "", 0, delLeft[0] + 1, cntr, 0);
    		else if (s[0] == '(') getAns(s, "", 0, delLeft[0], cntr - 1, 0);
    		else if (s[0] == ')') getAns(s, "", 0, delLeft[0], cntr + 1, 0);
    		else getAns(s, "", 0, delLeft[0], cntr, 0);
    		return ans;
    	}
    };
    

    This solution is based on depth-limited-DFS, and I judged whether a parenthesis must be removed, so that we can deal the problem without judge the string is valid or not.

    A right parenthesis must be removed when the string has no free left parenthesis before it, we can solve it in the function.

    To judge a left parenthesis cannot be solved in the function as we don't know the right part of the string, so we can use a array to record how many left parentheses must be removed after the parenthesis. if the remain number can be removed is no larger than that, the left parenthesis cannot be removed.

    We can sure a result string is valid with above improve, so that we can add it into the vector without scan it.


Log in to reply
 

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