當前位置:網站首頁>【棧+深度優先搜索】括號問題大匯總

【棧+深度優先搜索】括號問題大匯總

2022-05-14 19:37:14魔法攻城獅MRL

提示:如果本文對您有幫助,歡迎點贊支持!

目錄

前言

一、判斷一個括號字符串是否有效

二、括號字符串無效的比特置

三、回溯生成多個括號字符串


前言

括號系列算法問題是經典的面試高頻題,括號系列題目的核心考點就是用棧和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();
}

 閱讀完本文,你將可以提交如下LeetCode題目:

類型LeetCode題目

判斷一個括號字符串是否有效

20. 有效的括號(簡單難度)

1614. 括號的最大嵌套深度(簡單難度)

括號字符串無效的比特置

1249. 移除無效的括號(中等難度)

32. 最長有效括號(困難難度)

678. 有效的括號字符串(中等難度)

回溯生成多個括號字符串

22. 括號生成(中等難度)

劍指 Offer II 085. 生成匹配的括號(中等難度)

面試題 08.09. 括號(中等難度)

301. 删除無效的括號(困難難度)


一、判斷一個括號字符串是否有效

給定一個包含若幹個左右括號的字符串,例如“()))()()()”,判斷其是否有效,有效是指:左括號後必須用相同類型的右括號閉合, 左括號必須以正確的順序閉合。

 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,說明左括號全部被匹配,否則剩餘左括號
 }

20. 有效的括號(簡單難度)

 給定一個包括 '(',')','{','}','[',']' 的字符串 s ,判斷字符串是否有效。

該題在上述描述中編程了多組括號,顯然通過計數方式也可以,但是繁瑣,我們可以借助棧:

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。

你需要從字符串中删除最少數目的 '(' 或者 ')' (可以删除任意比特置的括號),使得剩下的「括號字符串」有效。

點評 

最少需要移除的括號數量,我們可以借助棧找出所有不匹配的括號比特置,其分別是:

多餘的左括號和多餘的右括號,直接全部删除即可

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. 最長有效括號(困難難度)

給你一個只包含 '('')' 的字符串,找出最長有效(格式正確且連續)括號子串的長度。

點評

用棧模擬一遍,標記處所有無法匹配括號的比特置,例如 ")()((())"的mark為[1, 0, 0, 1, 0, 0, 0, 0],此題就變成了尋找最長的連續的0的長度

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;
    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;
    }
    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);
            }
        }
    }

    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;
    }
};

版權聲明
本文為[魔法攻城獅MRL]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/134/202205141803497377.html

隨機推薦