跳到主要内容

301.删除无效的括号

· 阅读需 3 分钟

1、题干​

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

深圳阿里Lazada笔试题T4，30min钟4道题，这道题没时间写

1d58c1fc375efb4172fc38ed625cfb94.gif


2、解题思路​

回溯+剪枝枚举所有可行的情况，遍历过程中判断合法子串只需要判断已选子串长度不为0且左括号被消耗完即 lc=0，详细逻辑见注释


3、代码​

var removeInvalidParentheses = function (s) {
    let res = [''];

    // 初始状态：字符串下标i，已选字符数组chars，左括号数量lc
    function backtrace(i, chars, lc) {
        // 合法子串，比较长度并填入最终结果
        if (!lc && chars.length && chars.length > res[0].length) res = [chars.join('')];
        else if (!lc && chars.length && chars.length === res[0].length) res.push(chars.join(''));

        // 下标越界，遍历结束
        if (i >= s.length - 1) return;

        // 遍历所有待选字符
        for (let j = i + 1; j < s.length; j++) {
            const c = s[j];
            // 剪枝：存在无法配对的右括号
            if (c === ')' && !lc) continue;
            // 剪枝：1、左括号比剩余子串更长；2、已选子串长度加上未遍历子串长度还是小于结果子串的长度
            if (lc > s.length - j || chars.length + s.length - j < res[0].length) break;

            // 选择当前字符
            chars.push(c);
            // 递归搜索
            backtrace(j, chars, c === '(' ? lc + 1 : (c === ')' ? lc - 1 : lc));
            // 撤销选择
            chars.pop();
        }
    }

    // 初始状态：字符串下标i为-1，已选字符数组chars为空数组，左括号数量lc为0
    backtrace(-1, [], 0);

    return [...new Set(res)];
};

4、执行结果​

image.png