301. 删除无效的括号 (opens new window)

Description

Difficulty: 困难

Related Topics: 广度优先搜索 (opens new window), 字符串 (opens new window), 回溯 (opens new window)

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

Solution

Language: JavaScript

方法1:bfs

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

写一个函数，专门判断是否是有效的字符串

使用队列，队头出队，while循环判断队头字符串是否有效，若有效，放入res

若无效，则依次删除这个字符串的所有括号，并进行判重后将其再入队，以便之后再判断次字符串删了一个括号是否是有效的

因为要删除最小数量的无效括号，所以while循环中，一旦出现有效字符串，退出循环

/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function (s) {
    let res = [];
    let queue = [];
    let visited = new Set();//去重

    queue.push(s);
    while (true) {
        let size = queue.length;//[s]
        for (let i = 0; i < size; i++) {
            s = queue.shift();//出队
            if (isVaild(s)) {//如果是合法字符串
                res.push(s);//加入结果数组
            } else if (res.length == 0) {//不合法并且res.length == 0 则进入bfs下一层 尝试删除字符
                for (let i = 0; i < s.length; i++) {
                    if (s[i] == '(' || s[i] === ')') {//是左右括号尝试删除字符，否则跳过
                        let nexts = s.substring(0, i) + s.substring(i + 1);
                        if (!visited.has(nexts)) {//判断新生成的字符串是否重复
                            queue.push(nexts);//加入队列 进入下一层 [s1,s2...]
                            visited.add(nexts);//加入去重数组
                        }
                    }
                }
            }
        }
        if (res.length > 0) {//出现合法字符串的那一层，终止循环
            break;
        }
    }
    return res;
};

function isVaild(s) {
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {//左括号count+1
            count++;
        } else if (s[i] === ')') {//右括号count-1
            count--;
        }
        if (count < 0) {//小于0 说明右括号多
            return false;
        }
    }
    return count === 0;
}