題目
給定一個只包括 '('，')'忆谓，'{'，'}'踱承，'['倡缠，']' 的字符串，判斷字符串是否有效
有效字符串需滿足：
左括號必須用相同類型的右括號閉合茎活。
左括號必須以正確的順序閉合昙沦。
注意空字符串可被認為是有效字符串。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
解題
public boolean isValid(String s) {
//先用map把括號對存起來载荔，key：左括號盾饮；value：右括號；
// 這樣配對起來時間復雜度就為O(1);
//防止棧為空時報錯懒熙，加入('?','?')
Map<Character,Character> map = new HashMap<Character,Character>();
map.put('(',')');
map.put('[',']');
map.put('{','}');
map.put('?','?');
//排除幾種特殊情況：
if(s.equals("")){
return true;
}
if(s.length()%2==1){
return false;
}
if(s.charAt(0)==')'||s.charAt(0)==']'||s.charAt(0)=='}'){
return false;
}
//初始化棧丘损，然后循環(huán)s,如果是左括號，先入棧煌珊，并且把它放在stack的last号俐；
//如果有跟它配對的右括號出現(xiàn)，就將它移除定庵，如果最后正好都配對完吏饿，剩下的就是最開始的那個'？'
LinkedList<Character> stack = new LinkedList<Character>();
stack.add('?');
for(Character c:s.toCharArray()){
//map如果包含key蔬浙，證明就還是左括號
if(map.containsKey(c)){
stack.addLast(c);
// map不包括key了猪落，那證明應該是出現(xiàn)了一個右括號，如果符合一對括號畴博，
// 那它和棧里面的最后一個括號之間笨忌，肯定不能有其他形式的括號
// 所以把棧里的最后一個從map里get出來，看是否跟右括號一樣
}else if(map.get(stack.removeLast())!=c){
return false;
}
}
return stack.size()==1;
}
j結果
執(zhí)行用時 :5 ms, 在所有 Java 提交中擊敗了79.77%的用戶
內(nèi)存消耗 :35.1 MB, 在所有 Java 提交中擊敗了82.28%的用戶
