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).

Thoughts

看到all possible想到搜索。从一个不删遍历, 依次删一个, 两个...依次类推.由于删((中任何一个(效果是一样的，因此还引入一个visited来减少时间。

Code

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        queue<string> q;
        q.push(s);
        bool found = false;
        unordered_set<string> visited;
        while (!q.empty()) {
            const auto size = q.size();
            for (int i = 0; i < size; ++i) {
                string s = q.front();
                q.pop();
                if (visited.find(s) != visited.end()) continue;
                visited.insert(s);
                if (valid(s)) {
                    res.push_back(s);
                    found = true;
                    continue;
                }
                if (!found) {
                    for (int j = 0; j < s.size(); ++j) {
                        if (s[j] != '(' && s[j] != ')') continue;
                        q.push(s.substr(0, j).append(s.substr(j + 1, s.size())));
                    }
                }
            }
        }

        return res;
    }

private:
    bool valid(string s) {
        int val = 0;
        for (const auto c : s) {
            if (c == '(') ++val;
            if (c == ')') --val;
            if (val < 0) return false;
        }
        return val == 0;
    }
};

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();

        Queue<String> queue = new LinkedList<>();
        queue.add(s);
        boolean reached = false;
        Set<String> visited = new HashSet<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String str = queue.poll();
                if (visited.contains(str)) {
                    continue;
                }
                visited.add(str);
                if (isValid(str)) {
                    res.add(str);
                    reached = true;
                    continue;
                }

                if (reached) {
                    continue;
                }

                for (int j = 0; j < str.length(); j++) {
                    if (str.charAt(j) != '(' && str.charAt(j) != ')') {
                        continue;
                    }
                    String ns = str.substring(0, j) + str.substring(j + 1);
                    queue.add(ns);
                }
            }
        }

        return res;
    }

    private boolean isValid(String str) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (!stack.isEmpty() && stack.peek() == '(') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

Analysis

Errors: 1. str.charAt(j) != '(' && str.charAt(j) != ')

在第一层, 删0个, 选择0个字符有1种方法, 每种方法检查isValid耗时O(N), 总耗时O(N) 在弟二层, 删1个, 选择1个字符有C_N^1种方法, 每种方法检查isValid耗时O(N - 1), 总耗时N * (N-1) ... 在第N - 2层, 删N - 1个, 选择N - 1个字符有N种, ...总耗时N.

总耗时 N * 2 ^ (N - 1).