# 0301. 删除无效的括号

### 题目地址(301. 删除无效的括号)

<https://leetcode-cn.com/problems/remove-invalid-parentheses/>

### 题目描述

```
删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。

说明: 输入可能包含了除 ( 和 ) 以外的字符。

示例 1:

输入: "()())()"
输出: ["()()()", "(())()"]
示例 2:

输入: "(a)())()"
输出: ["(a)()()", "(a())()"]
示例 3:

输入: ")("
输出: [""]

```

### 前置知识

* BFS
* 队列

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

我们的思路是先写一个函数用来判断给定字符串是否是有效的。 然后再写一个函数，这个函数 依次删除第i个字符，判断是否有效，有效则添加进最终的返回数组。

这样的话实现的功能就是， 删除`一个` 小括号使之有效的所有可能。因此只需要递归调用`依次删除第i个字符`的功能就可以了。

而且由于题目要求是要删除最少的小括号，因此我们的思路是使用广度优先遍历，而不是深度有限的遍历。

![301.remove-invalid-parentheses](https://p.ipic.vip/sm267s.jpg)

> 没有动图，请脑补

### 关键点解析

* 广度优先遍历
* 使用队列简化操作
* 使用一个visited的mapper， 来避免遍历同样的字符串

### 代码

```js
var isValid = function(s) {
  let openParenthes = 0;
  for(let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      openParenthes++;
    } else if (s[i] === ')') {
      if (openParenthes === 0) return false;
      openParenthes--;
    }
  }
  return openParenthes === 0;
};
/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function(s) {
  if (!s || s.length === 0) return [""];
  const ret = [];
  const queue = [s];
  const visited = {};
  let current = null;
  let removedParentheses = 0; // 只记录最小改动

  while ((current = queue.shift())) {
    let hit = isValid(current);
    if (hit) {
      if (!removedParentheses) {
       removedParentheses =  s.length - current.length
      }
      if (s.length - current.length > removedParentheses) return ret.length === 0 ? [""] : ret;;
      ret.unshift(current);
      continue;
    }
    for (let i = 0; i < current.length; i++) {
      if (current[i] !== ')' && current[i] !== '(') continue;
      const subString = current.slice(0, i).concat(current.slice(i + 1));
      if (visited[subString]) continue;
      visited[subString] = true;
      queue.push(subString);
    }
  }

  return ret.length === 0 ? [""] : ret;
};
```

### 扩展

相似问题:

[validParentheses](https://github.com/azl397985856/leetcode/blob/master/problems/validParentheses.md)


---

# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/301.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.