有效的括弧(20)

題目描述

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字元串 s ，判斷字元串是否有效。

有效字元串需滿足：

左括弧必須用相同類型的右括弧閉合。
左括弧必須以正確的順序閉合。
每個右括弧都有一個對應的相同類型的左括弧。

大體思路

這裡我們使用棧這個數據結構來解決，我們從左到右依次遍歷，如果是左括弧我們就添加一個對應的右括弧進入到棧中，然後當我們遍歷到右括弧的時候我們需要比對當前棧頂元素是不是和當前遍歷到的右括弧一致，如果一致則彈出棧，如果不一致則說明此時閉合沒按照順序進行和我們的題目要求的不一致，如果我們遍歷到棧為空，而此時我們還有括弧元素沒有遍歷完，則說明此時沒有左括弧來和剩餘的右括弧進行匹配了，也是不符合題目要求的

代碼解析

class Solution {
    public boolean isValid(String s) {

        if (s.length() == 1) {
            return false;
        }

        Map<Character, Character> zuo = new HashMap<>();
        zuo.put('(', ')');
        zuo.put('{', '}');
        zuo.put('[', ']');
        Map<Character, Character> you = new HashMap<>();
        you.put(')', '(');
        you.put('}', '{');
        you.put(']', '[');

        //這是作為一個判斷依據，如果你這這個S中全都是左括弧的話就返回false;
        boolean temp = false;
        Stack<Character> stack = new Stack<>();
        //這裡如果是上來就是右括弧開頭的就不符合題目要求，直接返回
        if (you.containsKey(s.charAt(0))) {
            return false;
        }
        for (int i = 0; i < s.length(); i++) {
            if (zuo.containsKey(s.charAt(i))) {
                stack.push(zuo.get(s.charAt(i)));
            } else {
                //到這裡已經說明S中包含右括弧了，不全是左括弧了
                temp = true;

                //這裡是判斷棧如果為空，但此時S中還有元素沒有遍歷完，那就不能按照我們題目要求的順序進行閉合了，我們直接返回false
                if (stack.isEmpty() && i <= s.length() - 1) {
                    return false;
                } else if (s.charAt(i) == stack.peek()) {
                    stack.pop();
                    continue;
                } else {
                    return false;
                }
            }
        }

        if (temp == false || !stack.isEmpty()) {
            return false;
        }

        return true;
    }
}