兩分鐘看懂有效的括號
大家好，我是程序員吳師兄，今天跟大家分享一道和 棧 有關(guān)的題目，超級簡單也超級容易理解，這道題目曾經(jīng)出現(xiàn)在 bilibili 的面試中。
一、題目描述
給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。 左括號必須以正確的順序閉合。
示例 1：
輸入：s = "()"
輸出：true
示例 2：
輸入：s = "([)]"
輸出：false
提示：
1 <= s.length <= 104 s 僅由括號 '()[]{}' 組成
二、題目解析
我們用 四步分析法 來分析一下這道題目。
模擬：模擬題目的運行。
規(guī)律：嘗試總結(jié)出題目的一般規(guī)律和特點。
匹配：找到符合這些特點的數(shù)據(jù)結(jié)構(gòu)與算法。
邊界：考慮特殊情況。
1.模擬
有效的情況：
1）不嵌套
2）嵌套
無效的情況：
1）長度為奇數(shù)，左括號多余
2）長度為奇數(shù)，右括號多余
3）長度為偶數(shù)，左括號與右括號不配對
4）長度為偶數(shù)，部分子表達式可以配對，但外部不配對
2.規(guī)律
通過上述的模擬，可以總結(jié)出以下 3 個特點：
1、( 與 ）、[ 與 ]、{ 與 } 是一一對應(yīng)的關(guān)系，無法配對是無效的 2、對于有效的括號，它的部分子表達式仍然是有效的括號，比如 { [ ( ) ]} ，如果部分子表達式無效，那么整體都是無效的 3、部分子表達式如果建立了配對關(guān)系，是有效的括號，那么 消除 后是不會影響整體的 4、奇數(shù)長度的字符串總是無效的。
3.匹配
整個過程分為兩步，一個是配對，一個是消除。
配對 過程，（ 與 ）、[ 與 ]、{ 與 }。
消除 的過程是由內(nèi)向外進行，先判斷能否消除部分子表達式（內(nèi)），再判斷能否消除整體表達式（外），但在遍歷的過程卻是由外向內(nèi)進行遍歷，需要保存狀態(tài)，棧 先進后出的特點符合要求。
4.邊界
所謂邊界，即特殊情況：
字符串的長度為奇數(shù)
三、動畫圖解
四、參考代碼
// 登錄 https://www.algomooc.com 查看更多圖解
class Solution {
public boolean isValid(String s) {
// 當(dāng)字符串長度為奇數(shù)的時候，屬于無效情況
// 條件說明了長度至少為 1，所以不需要在判空
if (s.length() % 2 == 1) {
return false;
}
//構(gòu)建棧
Stack<Character> stack = new Stack<Character>();
//由外向內(nèi)遍歷字符串
for(char c : s.toCharArray()){
if(c == '('){
stack.push(')');
}else if(c == '['){
stack.push(']');
}else if( c == '{'){
stack.push('}');
}else if( stack.isEmpty() || c != stack.pop()){
//表明有多余的括號
return false;
}
}
return stack.isEmpty();
}
}
五、復(fù)雜度分析
時間復(fù)雜度
時間復(fù)雜度為 O(N)。需要遍歷一遍字符串。
空間復(fù)雜度
空間復(fù)雜度 O(N)。最壞情況下，棧的大小將是輸入字符串的長度。
六、參考引用
1、https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/
2、https://t10.lagounews.com/aR44RbR+c190C