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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/search/remove-invalid-parentheses.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.