括号匹配的两种栈（Java）

思想不难，记住左侧入栈，右侧匹配就行了。
顺提一下，手动维护栈真的很爽

使用类库 栈：

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        if(s==null || s.trim().length() == 0){
            return true;
        }
        int len = s.length();
        if(len % 2 != 0){
            return false;
        }

        LinkedList<Character> stack = new LinkedList<Character>();
        char[] chars = s.toCharArray();
        Set<Character> set = new HashSet<>(Arrays.asList('(', '[', '{'));
        for(char ch:chars){
            // 左括号入栈，右括号匹配
            if(set.contains(ch)){
                stack.push(ch);
            }else{
                // 匹配失败则返回false,右括号找不到左括号，那也是匹配失败！
                // match 匹配成功返回true，且左侧都位于栈中，实参顺序要注意
                if(stack.isEmpty() || !match(stack.pop(), ch)){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }


    public boolean match(char left,char right){
        switch(left){
            case '(':
                return right==')';
            case '[':
                return right==']';
            case '{':
                return right=='}';
            default:
                return false;
        }
    }
}

手动维护栈：

import java.util.*;
/**
* 降级，挑战基础
* 使用基本类型！效率拉满
* 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
* 内存消耗：36.5 MB, 在所有 Java 提交中击败了87.94%的用户
*/
public class Solution {

    public boolean isValid (String s) {
        if(s==null || s.trim().length() == 0){
            return true;
        }
        int len = s.length();
        if(len % 2 != 0){
            return false;
        }
         // 手动栈！先进后出,使用基本类型提高效率
        char[] stack = new char[len];
        int pointer = 0;
        char[] chars = s.toCharArray(); 

        for (char ch : chars) {
            // 如果是左侧，先入栈;右侧则匹配
            if (ch == '(' || ch == '[' || ch == '{') {
                stack[pointer++] = ch;
            } else {
                // 遇到右侧且栈空，直接结束,匹配不上也为false
                if (pointer == 0 || !match(stack[--pointer], ch)) {
                    return false;
                }
            }
        }
        // 栈空说明匹配完成，返回true
        return pointer == 0;
    }

    public boolean match(char left,char right){
        switch(left){
            case '(':
                return right==')';
            case '[':
                return right==']';
            case '{':
                return right=='}';
            default:
                return false;
        }
    }
}