「算法刷题」LeetCode的括号问题汇总

[TOC]

​ 括号系列算法问题是经典的面试高频题，括号系列题目的核心考点就是用栈和DFS 算法。对于括号问题，要明白如下2条规律：

一个「合法」的括号字符串一定满足如下2个条件：

1、括号字符串中的左括号数量一定等于右括号数量。

2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。

借助栈，我们可以查找一个合法字符串中的所有不合法位置:

// 用栈模拟一遍，标记处所有无法匹配括号的位置
// 例如 ")()((())"的mark为[1, 0, 0, 1, 0, 0, 0, 0]
stack<int> stk;
vector<int> mark(s.length(),0);
for(int i=0;i<s.length();++i){
    if(s[i]=='(') stk.push(i);
    else if(!stk.empty()&&s[i]==')')stk.pop();
    else mark[i]=1;// 多余的右括号需要标记
}
// 多余的左括号需要比较
while(!stk.empty()){
    mark[stk.top()]=1;
    stk.pop();
}

一、判断一个括号字符串是否有效

20. 有效的括号（简单难度）

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

有效字符串需满足：

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

点评：

该题是判断一个字符串中的左括号和右括号是否匹配，请注意该题目中有多种括号，如果只有一种括号,我们直接使用计数就可以判断：

 bool isValid(const string & s) {
     int cnt = 0;
     // 判断括号字符串是否合法
     for (int i = 0; i < s.size(); i++) {
         if (s[i] == '(') cnt++;// 遇到左括号计数+1
         else if (cnt>0&&s[i] == ')') cnt--;// 遇到右括号且计数>0,说明可以消耗一个计数
         else return false;
     }
     return cnt == 0;//如果计数=0，说明左括号全部被匹配，否则剩余左括号
 }

遇到左括号就入栈，遇到右括号就去和栈顶元素进行匹配，注意，每次匹配时如果栈为空就返回false：

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for(int i=0;i<s.length();++i) {
            // 如果遇到左括号，入栈其对应的右括号
            if(s[i]=='(') stk.push(')');
            else if(s[i]=='{') stk.push('}');
            else if(s[i]=='[') stk.push(']');
            // 如果遇到右括号，和栈顶元素对比：相等且栈不空就出栈
            else if(!stk.empty()&&s[i]==stk.top())stk.pop(); 
            else return false;
        }
        return stk.size()==0;
    }
};

1614. 括号的最大嵌套深度（简单难度）

给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。

输入：s = “(1)+((2))+(((3)))” 输出：3

点评

最大嵌套深度显然是连续的左括号或者右括号构成的，中间没有右括号来消耗，我们统计栈的大小即可

class Solution {
public:
    int maxDepth(string s) {
        int res=0;
        stack<char> stk;
        // 遍历字符串，遇到左括号就入栈，遇到右括号就出栈，统计栈每次的最大深度
        for(char c:s){
            if(c=='(') stk.push(')');
            else if(!stk.empty()&&stk.top()==c) stk.pop();
            int a=stk.size();
            res=max(res,a);
        }
        return res;
    }
};

二、括号字符串无效的位置

1249. 移除无效的括号（中等难度）

输入一个由 ‘(‘、’)’ 和小写字母组成的字符串 s，请从该字符串中删除最少数目的 ‘(‘ 或者 ‘)’ （可以删除任意位置的括号)，使得剩下的「括号字符串」有效，输出一种删除后的字符串。

输入：s = “lee(t(c)o)de)” 输出：”lee(t(c)o)de” 解释：”lee(t(co)de)” , “lee(t(c)ode)” 也是一个可行答案。

点评

最少需要移除的括号数量，我们可以借助栈找出所有不匹配的括号位置，其分别是：

多余的左括号和多余的右括号，直接全部删除即可

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        // 使用栈将所有无法匹配的位置设置为空格
        stack<int> stk;
        for(int i=0;i<s.length();++i){
            if(s[i]=='(') stk.push(i);
            else if(!stk.empty()&&s[i]==')') stk.pop();
            else if(stk.empty()&&s[i]==')') s[i]=' ';// 多余的右括号
        }
        while(!stk.empty()){
            int i=stk.top();
            s[i]=' ';// 多余的左括号
            stk.pop();
        }
        // 遍历字符串，将空格去除
        string res;
        for(char c:s) {
            if(c!=' ') res+=c;
        }
        return res;
    }
};

32. 最长有效括号（困难难度）

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

点评

LeetCode官方使用了动态规划、栈和双指针法

class Solution {
public:
    int longestValidParentheses(string s) {
        // 用栈模拟一遍，标记处所有无法匹配括号的位置
        // 例如 ")()((())"的mark为[1, 0, 0, 1, 0, 0, 0, 0]
        stack<int> stk;
        vector<int> mark(s.length(),0);
        for(int i=0;i<s.length();++i){
            if(s[i]=='(') stk.push(i);
            else if(!stk.empty()&&s[i]==')')stk.pop();
            else mark[i]=1;// 多余的右括号需要标记
        }
        // 多余的左括号需要比较
        while(!stk.empty()){
            mark[stk.top()]=1;
            stk.pop();
        }
        // 此题就变成了寻找最长的连续的0的长度
        int res=0;
        int len=0;
        for(int i=0;i<s.length();++i){
            if(mark[i]) len=0;
            else{
                len++;
                res=max(res,len);
            }
        }
        return res;
    }
};

678. 有效的括号字符串（中等难度）

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。

其中*可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。

点评

该题的难点是添加了一个具有通配效果的星号字符，我们可以使用一个专门的栈来放入该字符。

需要匹配右括号时，先检查是否有左括号匹配，没有左括号再检查是否有星号匹配；

当需要匹配多余的左括号时，先检查是否星栈中是否存在索引大的字符，有则匹配，没有则无法匹配。

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> left,star;// 左栈存储'(',星栈存储'*'
        // 遍历括号字符串
        for(int i=0;i<s.length();++i){
            // 左括号和星号入栈
            if(s[i]=='(') left.push(i);
            else if(s[i]=='*') star.push(i);
            // 右括号出栈
            else if(!left.empty()&&s[i]==')')left.pop();//先尝试出左括号
            else if(!star.empty()&&s[i]==')')star.pop();//再尝试出星号
            else return false;// 存在多余的右括号无法被匹配
        }
        // 多余的左括号需要匹配
        while(!left.empty()&&!star.empty()){
            // 如果左括号索引<星号索引,可以匹配
            if(left.top()<star.top()) {
                left.pop();
                star.pop();
            }
            else return false;
        }
        return left.empty();//如果左括号还不为空则false
    }
};

三、回溯生成多个括号字符串

22. 括号生成（中等难度）

剑指 Offer II 085. 生成匹配的括号（中等难度）

面试题 08.09. 括号（中等难度）

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

点评：

由于有效的括号字符串中左括号数量一定等于右括号数量，所以每个括号组合中一定有n个左括号和n个右括号。

我们可以尝试放入一个左括号或右括号来进行回溯遍历，终止条件是：

1、从左向右添加括号字符，当右括号数量大于左括号数量时一定不符合

2、左右括号数量任何一个超过n就一定不符合

3、左括号数量==右括号数量==n时就一定找到了一个合法的组合

class Solution {
public:
    vector<string> res;
    string path;
    // 左括号的数量、右括号的数量
    void dfs(int n,int left,int right){
        if(right>left) return;// 从左向右添加括号字符，当右括号多的时候就一定不符合
        if(left>n||right>n) return;// 如果有某个括号超过一半，则一定不是合法的
        // 如果左右括号恰好都为n
        if(left==n&&right==n){
            res.push_back(path);
            return ;
        }
        // 先尝试放入左括号
        path.push_back('(');
        dfs(n,left+1,right);
        path.pop_back();
        // 再尝试放入右括号
        path.push_back(')');
        dfs(n,left,right+1);
        path.pop_back();
    }
    vector<string> generateParenthesis(int n) {
        dfs(n,0,0);
        return res;
    }
};

301. 删除无效的括号（困难难度）

输入一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。返回所有可能的结果。答案可以按 任意顺序 返回。

示例 2：

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

点评

这道题和1249的区别在于，1249题只需要返回一种最少删除无效括号的情况就行，我们只要能找出一种所有不匹配的括号位置，将其删除即可，这些不匹配的括号位置依赖于我们从左向右搜素的顺序。

该题要返回所有最少删除的括号数量的情况，我们借助栈从左向右查找不匹配顺序只能找到其中一种情况；

我们可以使用回溯，先统计字符串中所有的要删除的左右括号数量

对每个左括号或者右括号字符都尝试删除，然后搜索所有情况，显然终止条件是：

1、剩余的要删除的括号数量>字符串剩余数量

2、如果左括号和右括号正好删够，并且是合法字符串

class Solution {
public:
    vector<string> res;
    void dfs(string& str, int start, int lremove, int rremove) {
        // 如果剩余的字符无法满足去掉的数量要求，直接返回
        if (lremove + rremove > str.size()) return;
        // 如果左括号和右括号正好删够，并且是合法字符串
        if (lremove == 0 && rremove == 0&&isValid(str)) {
            res.push_back(str);
            return;
        }
        // 每个节点从str的[start,:)，尝试分别删除左右括号
        for (int i = start; i < str.size(); i++) {
            // 如果同一层分支相同，则直接跳过
            if (i>start && str[i] == str[i - 1]) continue;
            // 尝试去掉一个左括号
            if ( str[i] == '(') {
                string tmp=str.substr(0, i)+str.substr(i + 1);
                dfs(tmp, i, lremove - 1, rremove);
            }
            // 尝试去掉一个右括号
            if ( str[i] == ')') {
                string tmp=str.substr(0, i)+str.substr(i + 1);
                dfs(tmp, i, lremove, rremove - 1);
            }
        }
    }
    vector<string> removeInvalidParentheses(string s) {
        int lremove = 0;// 需要删除的左括号数量
        int rremove = 0;// 需要删除的右括号数量
        // 遍历字符串，统计要删除的左括号和右括号的数量
        for (char c : s) {
            if (c == '(') lremove++;
            else if (lremove != 0&&c == ')') lremove--;
            else if (lremove == 0&&c == ')') rremove++;// 要删除的右括号
        }
        dfs(s, 0, lremove, rremove);
        return res;
    }
    

    inline bool isValid(const string & s) {
        int cnt = 0;
        // 判断括号字符串是否合法
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                cnt++;
            } else if (s[i] == ')') {
                cnt--;
                if (cnt < 0) {
                    return false;
                }
            }
        }
        return cnt == 0;
    }
};