[LeetCode]Remove Invalid Parentheses

这道题我们要明确几点：

• 删除最少的括号让string变valid，我们可能只删除左括号，()(；只删除右括号, ())；或者两个都删除，例如)(。所以我们需要先从左往右扫一遍删除不valid的左括号之后再反向扫一遍删除右括号。
• 去重。重复的来源是连续的左括号和右括号，例如()))和((()，如果我们如果我们不限定删除哪两个，那么就会产生重复。所以我们对于这种情况的策略是，永远从连续区间的第一个开始删。
• 删除哪些括号。对于()()())，我们可以分别删除第1,2,3个右括号从而得到(()()), ()(()),()()()。显然当我们从左向右扫遇到第一个invalid的右括号时，也就是没有足够的左括号可以match它，这代表我们必须要删除一个右括号来使得序列合法。我们可以从头开始分别将每一个不产生重复的右括号删除（这样不会有问题，因为之前的每一个左括号还是有对应的右括号match），继续递归。并且记录这一次删除的位置，下一层递归要删除的话继续从这之后开始。

实现的时候，对于从左向右和从又向左的两个扫描，我们可以共用一套代码，第二次从右向左扫描的时候，我们把string做一个镜像即可。假设string长度为n，空间复杂度worst case O(n)，递归深度。时间复杂度O(n)，从左到右两个指针最多走一遍，再从右到左一次，代码如下：

	class Solution {
	public:
	vector<string> removeInvalidParentheses(string s) {
	vector<string> res;
	backtracking(res, s, 0, 0, false);
	return res;
	}
	private:
	void backtracking(vector<string>& res, string s, int start, int lastD, bool rev)
	{
	int count = 0;
	for(int i = start; i < s.size(); ++i)
	{
	if(s[i] == '(')++count;
	if(s[i] == ')')--count;
	if(count < 0)
	{
	for(int j = lastD; j <= i; ++j)
	{
	if(s[j] == ')' && (!j || s[j - 1] != ')'))
	backtracking(res, s.substr(0, j) + s.substr(j + 1), i, j, rev);
	}
	return;
	}
	}
	if(!rev)
	backtracking(res, mirror(s), 0, 0, true);
	else
	res.push_back(mirror(s));
	}
	string mirror(string s)
	{
	string res;
	for(int i = s.size() - 1; i >= 0; --i)
	{
	res += s[i] == ')'? '(': (s[i] == '('? ')': s[i]);
	}
	return res;
	}
	};

view raw Remove Invalid Parentheses.cpp hosted with ❤ by GitHub

这道题和POJ 1141也是类似的。1141是求添加多少个括号可以使得序列合法并且只要输出一个合法串。这道题是删除，当然这道题的输入还包含了字母，这个比较好解决，输出的时候我们要输出所有的结果，这代表我们记录路径的时候要记录所有的最优分割点，之后我们递归地生成所有结果即可。DP解法比较麻烦的一点是没有比较好的去重的方法，这里我们用unordered_set来去重。除此之外，我们可以看到DP解法的时间空间复杂度也比DFS要差，需要O(n^2)，所以还是DFS解法更好。代码如下：

	class Solution {
	public:
	vector<string> removeInvalidParentheses(string s) {
	int len = s.size();
	//dp[i][j] represents minimum cost to make substring s[i, j] to be palindrome
	//dp[i][j] = dp[i + 1][j], if s[i] is alpha
	//dp[i][j] = dp[i + 1][j] + 1, if s[i] == ')'
	//else, dp[i][j] = min(dp[i + 1][k - 1] + dp[k + 1][j]), i <= k <= j and s[k] == ')'
	//use path to record the cut point for every [i, j]
	//we are using vector<int> because there may be ties and [i, j] can be broken at multiple points
	vector<vector<int>> dp(len + 1, vector<int>(len + 1, 0));
	unordered_map<int, vector<int>> path;
	for(int i = 0; i < len; ++i)if(!isalpha(s[i]))dp[i][i] = 1;
	for(int j = 0; j < len; ++j)
	{
	for(int i = j - 1; i >= 0; --i)
	{
	int key = i * len + j;
	if(isalpha(s[i]))
	{
	dp[i][j] = dp[i + 1][j];
	path[key].push_back(-1);
	continue;
	}
	//assume s[i] doesn't match
	dp[i][j] = dp[i + 1][j] + 1;
	path[key].push_back(-1);
	for(int k = i + 1; k <= j; ++k)
	{
	if(s[i] == '(' && s[k] == ')')
	{
	int cost = dp[i + 1][k - 1] + dp[k + 1][j];
	if(cost < dp[i][j])
	{
	dp[i][j] = cost;
	path[key].clear();
	path[key].push_back(k);//s[k] matches s[i]
	}
	else if(cost == dp[i][j])
	path[key].push_back(k);
	}
	}
	}
	}
	auto set = generate(s, 0, len - 1, len, path);
	vector<string> res;
	for(auto& str : set)res.push_back(str);
	return res;
	}
	private:
	unordered_set<string> generate(string& s, int i, int j, int len, unordered_map<int, vector<int>>& path)
	{
	//follow the cut point and generate results recursively
	if(i > j)return {""};
	if(i == j)
	{
	if(isalpha(s[i]))return {string(1, s[i])};
	else return {""};
	}
	auto cutPoints = path[i * len + j];
	unordered_set<string> res;
	int size = cutPoints.size();
	for(int n = 0; n < size; ++n)
	{
	int k = cutPoints[n];
	if(k == -1)
	{
	for(auto str : generate(s, i + 1, j, len, path))
	res.insert(isalpha(s[i])? s[i] + str: str);
	}
	else
	{
	unordered_set<string> lefts = generate(s, i + 1, k - 1, len, path);
	unordered_set<string> rights = generate(s, k + 1, j, len, path);
	for(auto& left : lefts)
	for(auto& right : rights)
	res.insert(s[i] == '('? "(" + left + ")" + right: left + right);
	}
	}
	return res;
	}
	};

view raw Remove Invalid Parentheses_dp.cpp hosted with ❤ by GitHub