LeetCode 301. Remove Invalid Parentheses - DFS case study by Huahualeetcode

Here is the link.



Here is the code example in C++.

I spent 25 minutes to watch the video. The explanation is very clear and very straightforward to apply BFS, no pruning. I do like to work on the solution first using DFS, make it work, and then think about more if I have time to add some pruning ideas. 

C++ code is also saved in a gist. Here is the gist.

I will write a C# solution using the same idea. 

	// Author: Huahua
	// Runtime: 0 ms
	class Solution {
	public:
	vector<string> removeInvalidParentheses(const string& s) {
	int l = 0;
	int r = 0;
	for (const char ch : s) {
	l += (ch == '(');
	if (l == 0)
	r += (ch == ')');
	else
	l -= (ch == ')');
	}
	vector<string> ans;
	dfs(s, 0, l, r, ans);
	return ans;
	}
	private:
	bool isValid(const string& s) {
	int count = 0;
	for (const char ch : s) {
	if (ch == '(') ++count;
	if (ch == ')') --count;
	if (count < 0) return false;
	}
	return count == 0;
	}
	// l/r: number of left/right parentheses to remove.
	void dfs(const string& s, int start, int l, int r, vector<string>& ans) {
	// Nothing to remove.
	if (l == 0 && r == 0) {
	if (isValid(s)) ans.push_back(s);
	return;
	}
	for (int i = start; i < s.length(); ++i) {
	// We only remove the first parenthes if there are consecutive ones to avoid duplications.
	if (i != start && s[i] == s[i - 1]) continue;
	if (s[i] == '(' || s[i] == ')') {
	string curr = s;
	curr.erase(i, 1);
	if (r > 0 && s[i] == ')')
	dfs(curr, i, l, r - 1, ans);
	else if (l > 0 && s[i] == '(')
	dfs(curr, i, l - 1, r, ans);
	}
	}
	}
	};

view raw Leetcode301RemoveInvalidParentheses.cpp hosted with ❤ by GitHub