301. 删除无效的括号

[webVueBlog]

301. 删除无效的括号

Description

Difficulty: 困难

Related Topics: 广度优先搜索, 字符串, 回溯

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

Solution

Language: JavaScript

/**
 * @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;
}