題目

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true

解題

public boolean isValid(String s) {
        //先用map把括號對存起來，key：左括號；value：右括號；
        // 這樣配對起來時間復(fù)雜度就為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了，那證明應(yīng)該是出現(xiàn)了一個右括號，如果符合一對括號，
//                那它和棧里面的最后一個括號之間，肯定不能有其他形式的括號
//                所以把棧里的最后一個從map里get出來，看是否跟右括號一樣
            }else if(map.get(stack.removeLast())!=c){
                return false;
            }
        }
        return stack.size()==1;
}

j結(jié)果

執(zhí)行用時 :5 ms, 在所有 Java 提交中擊敗了79.77%的用戶
內(nèi)存消耗 :35.1 MB, 在所有 Java 提交中擊敗了82.28%的用戶