給定一個只包括 '('，')'隧期，'{'飒责，'}'，'['仆潮，']' 的字符串 s 宏蛉，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合性置。
左括號必須以正確的順序閉合拾并。
示例 1：
輸入：s = "()"
輸出：true
示例 2：
輸入：s = "()[]{}"
輸出：true
示例 3：
輸入：s = "(]"
輸出：false
示例 4：
輸入：s = "([)]"
輸出：false
示例 5：
輸入：s = "{[]}"
輸出：true
方法一：棧
判斷括號的有效性可以使用「棧」這一數(shù)據(jù)結(jié)構(gòu)來解決鹏浅。
我們遍歷給定的字符串 ss嗅义。當(dāng)我們遇到一個左括號時，我們會期望在后續(xù)的遍歷中隐砸，有一個相同類型的右括號將其閉合之碗。由于后遇到的左括號要先閉合，因此我們可以將這個左括號放入棧頂季希。
當(dāng)我們遇到一個右括號時褪那，我們需要將一個相同類型的左括號閉合。此時式塌，我們可以取出棧頂?shù)淖罄ㄌ柌⑴袛嗨鼈兪欠袷窍嗤愋偷睦ㄌ柌┚础Ｈ绻皇窍嗤念愋停蛘邨Ｖ胁]有左括號峰尝，那么字符串 ss 無效偏窝，返回 \text{False}False。為了快速判斷括號的類型境析，我們可以使用哈希表存儲每一種括號囚枪。哈希表的鍵為右括號，值為相同類型的左括號劳淆。
在遍歷結(jié)束后链沼，如果棧中沒有左括號，說明我們將字符串 ss 中的所有左括號閉合沛鸵，返回 \text{True}True括勺，否則返回 \text{False}False缆八。
注意到有效字符串的長度一定為偶數(shù)，因此如果字符串的長度為奇數(shù)疾捍，我們可以直接返回 \text{False}False奈辰，省去后續(xù)的遍歷判斷過程。
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
來源：力扣（LeetCode）
著作權(quán)歸作者所有乱豆。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)奖恰，非商業(yè)轉(zhuǎn)載請注明出處。
class Solution {
public boolean isValid(String s) {
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
if (s.length()%2==1){
return false;
}
Deque<Character> stack = new LinkedList<Character>();
for (int i =0;i<s.length();i++){
char ch=s.charAt(i);
if (pairs.containsKey(ch)){
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
}else{
stack.push(ch);
}
}
return stack.isEmpty();
}
}
