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