題目
給定一個(gè)只包括 '('毁兆，')'浙滤，'{'，'}'气堕，'['纺腊，']' 的字符串畔咧，判斷字符串是否有效。
有效字符串需滿足：
左括號(hào)必須用相同類型的右括號(hào)閉合揖膜。
左括號(hào)必須以正確的順序閉合誓沸。
注意空字符串可被認(rèn)為是有效字符串。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/valid-parentheses
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有壹粟。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)拜隧，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
題解
一共有3種括號(hào)煮寡。每種括號(hào)可分為左括號(hào)和右括號(hào)虹蓄。我們可以模擬一個(gè)匹配的過(guò)程，沒(méi)有右括號(hào)都應(yīng)和一個(gè)左括號(hào)匹配上幸撕∞弊椋可以依次遍歷這些括號(hào)，遇到左括號(hào)時(shí)坐儿，我們不知道是否有右括號(hào)和它匹配律胀，所以應(yīng)該把它暫存起來(lái)。遇到右括號(hào)時(shí)貌矿，這時(shí)前面必須有一個(gè)正確的左括號(hào)和它匹配炭菌。
對(duì)于第一個(gè)遇到的右括號(hào)，和它匹配的一定是之前最后遇到的一個(gè)左括號(hào)逛漫，如果該左括號(hào)不匹配或不存在黑低，說(shuō)明匹配失敗。
如果能匹配成功酌毡，我們消去這一對(duì)括號(hào)克握。繼續(xù)判斷下一個(gè)括號(hào)的情況。再遇到右括號(hào)枷踏，繼續(xù)找之前的最后一個(gè)左括號(hào)（注意這里已經(jīng)去掉了匹配成功的括號(hào)菩暗，所以還是滿足和最后一個(gè)左括號(hào)匹配的條件）。
用一個(gè)stack存儲(chǔ)左括號(hào)旭蠕。
代碼
class Solution {
private static Map<Character,Character> map = new HashMap<Character,Character>();
static {
map.put(')','(');
map.put('}','{');
map.put(']','[');
}
public boolean isValid(String s) {
LinkedList<Character> stack = new LinkedList<Character>();
int length = s.length();
for(int i = 0; i < length; i++) {
char c = s.charAt(i);
if(map.containsKey(c)) {
char c1 = stack.isEmpty()? '#' : stack.pop();
if(!map.get(c).equals(c1)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
}
知識(shí)點(diǎn)
1.LinkedList可以作為棧使用停团。可以直接調(diào)用它的push和pop方法掏熬。
