20. 有效的括號 - 力扣（LeetCode）

/**

? ? ? ? 括號特性:

? ? ? ? ? ? ? ? 左括號必定先出現,每個左括號都需要一個右括號與之匹配,后出現的左括號先匹配

? ? ? ? 解法:

? ? ? ? ? ? ? ? 依據后出現的左括號先匹配,很容易聯想到棧,即后進先出

? ? ? ? ? ? ? ? 遍歷字符串,遇到左括號就在棧中添加一個對應的右括號

? ? ? ? ? ? ? ? 遇到右括號就彈出棧頂元素判斷是否一致(當前遍歷到的最后一個出現的左括號是否能閉合)

? ? ? ? ? ? 不合法: ? ?

? ? ? ? ? ? ? ? 若彈出的右括號與遇到的右括號不一致---> 左右類型不匹配,不合法

? ? ? ? ? ? ? ? 若遇到右括號時棧中無元素可彈出---> 右括號多余無法閉合,不合法

? ? ? ? ? ? ? ? 若字符串遍歷結束棧中仍有元素---> 左括號多余無法閉合,不合法

*/

class Solution {/**括號特性:左括號必定先出現,每個左括號都需要一個右括號與之匹配,后出現的左括號先匹配解法:依據后出現的左括號先匹配,很容易聯想到棧,即后進先出遍歷字符串,遇到左括號就在棧中添加一個對應的右括號遇到右括號就彈出棧頂元素判斷是否一致(當前遍歷到的最后一個出現的左括號是否能閉合)不合法:    若彈出的右括號與遇到的右括號不一致---> 左右類型不匹配,不合法若遇到右括號時棧中無元素可彈出---> 右括號多余無法閉合,不合法若字符串遍歷結束棧中仍有元素---> 左括號多余無法閉合,不合法*/public boolean isValid(String s) {//利用雙端隊列模擬棧Deque<Character> stack = new ArrayDeque<>();//按規則遍歷字符串for(char c : s.toCharArray()) {//將對應的右括號入棧if(c == '(') {stack.push(')');} else if(c == '[') {stack.push(']');} else if(c == '{') {stack.push('}');}//遇到右括號,判斷是否合法else {//右括號多余或左右類型不匹配 不合法if(stack.isEmpty() || stack.pop() != c) {return false;}}}//左括號多余if(!stack.isEmpty()) {return false;}return true;}
}