301. [✔][H]删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

输入：s = ")("
输出：[""]

提示：

• 1 <= s.length <= 25
• s 由小写英文字母以及括号 '(' 和 ')' 组成
• s 中至多含 20 个括号

---

题解：

最少删除的括号数量，这种求最短或者最少的题目，联想到bfs，bfs第一个出现解的层，即为最短删除括号所形成的合法字符串。准备queue对字符串进行bfs搜索，出现合法字符串入队，否则尝试删除一个字符，进入下一层判断，注意合法字符可能重复，需要去重。

作者：xiaochen1024 链接：https://leetcode.cn/problems/remove-invalid-parentheses/solution/301-shan-chu-wu-xiao-de-gua-hao-by-chen-p2m5h/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

// @lc code=start
function removeInvalidParentheses(s: string): string[] {
    const isVaild = (s: string) => {
        let count = 0;
        for (let i = 0; i < s.length; i++) {
            if (s[i] === "(") {
                count++;
            } else if (s[i] === ")") {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count === 0;
    }

    let res: string[] = [];
    let queue: string[] = [];
    let visited = new Set();

    queue.push(s);

    while (true) {
        let size = queue.length;

        for (let i = 0; i < size; i++) {
            let str = queue.shift()!;
            if (isVaild(str)) {
                res.push(str);
            } else if (res.length === 0) {//不合法并且res.length == 0 则进入bfs下一层 尝试删除字符
                for (let j = 0; j < str.length; j++) {
                    if (str[j] === "(" || str[j] === ")") {
                        let next = str.substring(0, j) + str.substring(j + 1);
                        if (!visited.has(next)) {
                            queue.push(next);
                            visited.add(next);
                        }
                    }

                }
            }
        }

        if (res.length > 0) {//出现合法字符串的那一层，终止循环
            break;
        }
    }

    return res;

};
// @lc code=end