大家好，我是程式員吳師兄，今天跟大家分享一道和 棧
一、題目描述
給定一個隻包括 '('，')'，'{'，'}'，'['，']' 的字元串 s ，判斷字元串是否有效。
有效字元串需滿足：
- 左括号必須用相同類型的右括号閉合。
- 左括号必須以正确的順序閉合。
示例 1：
輸入：s = "()"
輸出：true 示例 2：
輸入：s = "([)]"
輸出：false 提示：
- 1 <= s.length <= 104
- s 僅由括号 '()[]{}' 組成
二、題目解析
我們用 四步分析法
- 模拟：模拟題目的運作。
- 規律：嘗試總結出題目的一般規律和特點。
- 比對：找到符合這些特點的資料結構與算法。
- 邊界：考慮特殊情況。
1.模拟
有效的情況：
1）不嵌套
2）嵌套
無效的情況：
1）長度為奇數，左括号多餘
2）長度為奇數，右括号多餘
3）長度為偶數，左括号與右括号不配對
4）長度為偶數，部分子表達式可以配對，但外部不配對
2.規律
通過上述的模拟，可以總結出以下 3 個特點：
- 1、(與）、[與]、{與}是一一對應的關系，無法配對是無效的
- 2、對于有效的括号，它的部分子表達式仍然是有效的括号，比如{ [ ( ) ]}
- 3、部分子表達式如果建立了配對關系，是有效的括号，那麼消除
- 4、奇數長度的字元串總是無效的。
3.比對
整個過程分為兩步，一個是配對，一個是消除。
配對 過程，（ 與 ）、[ 與 ]、{ 與 }。
消除 的過程是由内向外進行，先判斷能否消除部分子表達式（内），再判斷能否消除整體表達式（外），但在周遊的過程卻是由外向内進行周遊，需要儲存狀态，棧
4.邊界
所謂邊界，即特殊情況：
- 字元串的長度為奇數
三、動畫圖解
四、參考代碼
// 登入 https://www.algomooc.com 檢視更多圖解
class Solution {
public boolean isValid(String s) {
// 當字元串長度為奇數的時候，屬于無效情況
// 條件說明了長度至少為 1，是以不需要在判空
if (s.length() % 2 == 1) {
return false;
}
//建構棧
Stack<Character> stack = new Stack<Character>();
//由外向内周遊字元串
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();
}
} 五、複雜度分析
時間複雜度
時間複雜度為 O(N)。需要周遊一遍字元串。
空間複雜度
空間複雜度 O(N)。哈希表和棧使用線性的空間大小，最壞情況下，棧的大小将是輸入字元串的長度。
六、參考引用
1、https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/