括号题库

2024年04月09日

柏拉文

越努力，越幸运

一、有效的括号

给定一个只包括 (，)，{，}，[，] 的字符串 s ，判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例1:

输入：s = "()"
输出：true

示例2:

输入：s = "()[]{}"
输出：true

1.1 通过栈

思路:

判断字符长度,有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 false，省去后续的遍历判断过程
对不同类型的括号建立 map ，key 为右括号，value 为左括号
从左到右遍历字符串，若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；

function isValid(s){
    const map = new Map([
        ["}","{"],
        [")","("],
        ["]",'[']
    ]);
    const stack = [];
    for(let char of s){
        if(map.has(char)){
            if(!stack.length || stack[stack.length-1] !== map.get(char)){
                return false;
            }
            stack.pop();
        }else{
            stack.push(char);
        }
    }
    return !stack.length;
}

性能分析:

时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。

二、最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例1:

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例2:

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例3:

输入：s = ""
输出：0

2.1 通过栈

思路: 始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标:

对于遇到的每个 ‘(’ ，我们将它的下标放入栈中
对于遇到的每个 ‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号:
- 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
- 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
我们从前往后遍历字符串并更新答案即可。

注意如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 -1 的元素。

function longestValidParentheses(s) {
    let result=0;
    let stack=[];
    stack.push(-1);
    for(let i=0;i<s.length;i++){
        if(s[i]=='('){
            stack.push(i);
        }else{
            stack.pop();
            if(stack.length==0){
                stack.push(i);
            }else{
                result=Math.max(result,i-stack[stack.length-1]);
            }
        }
    }
    return result;
};

性能分析:

时间复杂度: O(n)，n 是给定字符串的长度。我们只需要遍历字符串一次即可。
空间复杂度: O(n)。栈的大小在最坏情况下会达到 n，因此空间复杂度为 O(n) 。

2.2 动态规划

思路:

状态定义: dp[i]表示以下标i字符结尾的最长有效括号的长度
状态转移方程: 从前往后遍历字符串求解dp值，我们每两个字符检查一次
- s[i]=‘)’ 且s[i−1]=‘(’，也就是字符串形如“……()”，我们可以推出: dp[i]=dp[i−2]+2
- s[i]=‘)’ 且s[i−1]=‘)’，也就是字符串形如“……))”，我们可以推出: 如果 s[i−dp[i−1]−1]=‘(’，那么 dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2 处。
状态初始化:dp数组全部初始化为0

function longestValidParentheses(s) {
    let result=0;
    let dp=new Array(s.length).fill(0);
    for(let i=1;i<s.length;i++){
        if(s[i]==')'){
            if(s[i-1]=='('){
                dp[i]=(i>=2?dp[i-2]:0)+2;
            }else if(i-dp[i-1]>0&&s[i-dp[i-1]-1]=='('){
                dp[i]=dp[i-1]+((i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0)+2;
            }
            result=Math.max(result,dp[i]);
        }
    }
    return result;
};

性能分析:

时间复杂度： O(n)，其中 n 为字符串的长度。我们只需遍历整个字符串一次，即可将 dp 数组求出来。
空间复杂度： O(n)。我们需要一个大小为 n 的 dp 数组。

三、有效的括号字符串

给定一个只包含三种字符的字符串: （ ，） 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:

任何左括号 ( 必须有相应的右括号 )
任何右括号 ) 必须有相应的左括号 (
左括号 ( 必须在对应的右括号之前 )
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串
一个空字符串也被视为有效字符串

示例A:

输入: "()"
输出: True

示例B:

输入: "(*)"
输出: True

3.1 贪心

思路: 使用贪心的思想，可以将空间复杂度降到 O(1)。从左到右遍历字符串,遍历过程中,未匹配的左括号数量可能会出现如下变化:

如果遇到左括号，则未匹配的左括号数量加 1
如果遇到右括号，则需要有一个左括号和右括号匹配，因此未匹配的左括号数量减 1
如果遇到星号，由于星号可以看成左括号、右括号或空字符串，因此未匹配的左括号数量可能加 1、减 1 或不变

基于上述结论，可以在遍历过程中维护未匹配的左括号数量可能的最小值和最大值，根据遍历到的字符更新最小值和最大值:

如果遇到左括号，则将最小值和最大值分别加 1
如果遇到右括号，则将最小值和最大值分别减 1
如果遇到星号，则将最小值减 1，将最大值加 1

任何情况下，未匹配的左括号数量必须非负，因此当最大值变成负数时，说明没有左括号可以和右括号匹配，返回 false。当最小值为 0 时，不应将最小值继续减少，以确保最小值非负。遍历结束时，所有的左括号都应和右括号匹配，因此只有当最小值为 0 时，字符串 s 才是有效的括号字符串。

实现

function checkValidString(s){
    const { length } = s;
    let minCount = 0;
    let maxCount = 0;
    for(let i=0;i<length;i++){
        const char = s[i];
        if(char === "("){
            minCount++;
            maxCount++;
        }else if(char === ")"){
            minCount = Math.max(minCount-1,0);
            maxCount--;
            if(maxCount < 0){
                return false;
            }
        }else{
            minCount = Math.max(minCount-1,0);
            maxCount++;
        }
    }
    return minCount === 0;
}

一、有效的括号​

1.1 通过栈​

二、最长有效括号​

2.1 通过栈​

2.2 动态规划​

三、有效的括号字符串​

3.1 贪心​

一、有效的括号

1.1 通过栈

二、最长有效括号

2.1 通过栈

2.2 动态规划

三、有效的括号字符串

3.1 贪心