[LeetCode]Remove Invalid Parentheses

这道题我们要明确几点：

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

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

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