301. Remove Invalid Parentheses

https://leetcode.com/problems/remove-invalid-parentheses/description/

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]

"(a)())()" -> ["(a)()()", "(a())()"]

")(" -> [""]

Thoughts

由'('和')'组成的字符串，可移除任意个'('或')'使得给定字符串能配对成功，找出所有可能的移除量最少能形成的合法配对字符串。找出所有=>DFS。由于只有一种括号，判断是否合法可以遍历，当遇到"(" +1, 遇到")" - 1, 当成正数时说明)比(多, 要删), 全部遍历完不为0说明(比)多，倒着遍历删(。 基于此思想, 维护一个sum, 遍历s, 当count不为0则继续遍历, 当为负数则说明前面的prefix中有')'要被删掉。 遍历prefix, 把prefix中的')'删掉, 从当前位置和新的s继续DFS下去。 做完后保证s中')'是不多的, 但可能s中'('有多余的。 把string 翻转过来, 改成删'(', 重复此过程, 比如现在s是((()), 翻转得到))(((。 把)当作+1, (当作-1, 最后得到的s就是删除量最小的valid parentheses。为了防止出现重复结果，比如(()))删后面三个任意一个结果都是一样的，在遍历j时检查s[j - 1]是否等于)，是就跳过；还有()k)))，第一次sum<0时会触发删第一个)成(k)))和删第二个成()k))，其中()k))DFS又会再触发删第一个(，导致重复。所以还需要一个额外变量last记录上次删除到的位置，j从该位置开始遍历。

Code

/*
 * @lc app=leetcode id=301 lang=cpp
 *
 * [301] Remove Invalid Parentheses
 */

// @lc code=start
class Solution {
public:
    void dfs(string s, int pos, int last, vector<string> &res, vector<char> p) {
        int sum = 0;
        for (int i = pos; i < s.length(); ++i) {
            if (s[i] == p[0]) ++sum;
            else if (s[i] == p[1]) {
                --sum;
                if (sum >= 0) continue;
                for (int j = last; j <= i; ++j) {
                    if (s[j] == p[1] && (j == last || s[j - 1] != p[1])) {
                        dfs(s.substr(0, j) + s.substr(j + 1), i, j, res, p);
                    }
                }
                return;
            }
        }
        if (p[0] == '(' && sum > 0) {
            reverse(s.begin(), s.end());
            return dfs(s, 0, 0, res, {')', '('});
        }
        if (p[0] == ')') reverse(s.begin(), s.end());
        res.push_back(s);
    }

    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        dfs(s, 0, 0, res, {'(', ')'});
        return res;
    }
};
// @lc code=end

Analysis

暴力法dfs需要2 ^ N时间复杂度, 这种解法会好太多, 比如遍历到b时发现要删, 那T(N) = b / 2 T(N - b) + N , b / 2是因为前b个里头有b/ 2个')'可供选择, 拼接字符串需要耗时N. 根据[https://www.quora.com/How-do-I-solve-the-recurrence-T-n-T-n-1-+-n-using-masters-theorem], T(N) = O(N (b/2 ) ^ (N / b)).