301. Remove Invalid Parentheses - CPP - Solution


  • 0
    Y
    // 301. Remove Invalid Parentheses
    // https://leetcode.com/problems/remove-invalid-parentheses/
    #include <iostream>
    #include <cassert>
    #include <string>
    #include <vector>
    #include <unordered_set>
    #include <algorithm>
    #include <iterator> 
    using namespace std;
    class Solution {
    public:
    	vector<string> removeInvalidParentheses(string s) {
    		if (s.empty()) {
    			return vector<string>({""});
    		}
    		if (isValid(s)) {
    			return vector<string>({s});
    		}
    		unordered_set<string> result;
    		vector<unordered_set<string>> OPT(s.size() + 1);
    		OPT[s.size()].insert(s);
    		for (size_t len = s.size() - 1; len >= 1; len--) {
    			for (const auto &parent : OPT[len + 1]) {
    				for (size_t i = 0; i < parent.size(); i++) {
    					const string candidate = parent.substr(0, i) + parent.substr(i + 1, parent.size() - i);
    					if (isValid(candidate)) {
    						result.insert(candidate);
    						continue;
    					}
    					OPT[len].insert(candidate);
    				}
    			}
    			if (!result.empty()) {
    				return vector<string>(begin(result), end(result));
    			}
    		}
    		return vector<string>({""});
    	}
    private:
    	bool isValid(const string& s) {
    		vector<char> stack;
    		for (const auto &c : s) {
    			if (c == '(') {
    				stack.push_back(c);
    				continue;
    			}
    			if (c == ')') {
    				if (stack.empty()) {
    					return false;
    				}
    				stack.pop_back();
    				continue;
    			}
    		}
    		return stack.empty();
    	}
    };
    int main(void) {
    	Solution solution;
    	vector<string> result;
    
    	result = solution.removeInvalidParentheses("");
    	sort(begin(result), end(result));
    	assert(vector<string>({""}) == result);	
    
    	result = solution.removeInvalidParentheses("()())()");
    	sort(begin(result), end(result));
    	assert(vector<string>({"(())()", "()()()"}) == result);
    
    	result = solution.removeInvalidParentheses("(a)())()");
    	sort(begin(result), end(result));
    	assert(vector<string>({"(a())()", "(a)()()"}) == result);
    	
    	result = solution.removeInvalidParentheses(")(");
    	sort(begin(result), end(result));
    	assert(vector<string>({""}) == result);
    
    	result = solution.removeInvalidParentheses("(r(()()(");
    	sort(begin(result), end(result));
    	assert(vector<string>({"(r())", "(r)()", "r(())", "r()()"}) == result);
    
    	cout << "\nPassed All\n";
    	return 0;
    }
    

Log in to reply
 

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