leetcode 20 有效的括号——栈

一、题目描述

给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1:

输入:s = “()”
输出:true

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses

二、解题思路与代码

这是一道简单题,初看题目想了几种方法:双指针、递归、动态规划,但是都无从下手,最后瞟了眼题解,嘿嘿。思想还是很简单的,用栈先进先出的特性来解题,思路如下:
1.遍历字符串,将所有左括号入栈,遇到右括号时将栈顶元素弹出,判断是否匹配,若不匹配则返回false,匹配则继续遍历。
2.遍历完成后判断栈是否为空,不为空则表明没有完全匹配,返回false。
注意,遍历前可以先将奇数长度的字符串排除。
	public boolean isValid(String s) {
        if (s == null) {
            return false;
        }
        if (s.length() % 2 != 0) {
            return false;
        }
        Deque<Character> stack = new ArrayDeque<>();
       
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ')' || ch == ']' || ch == '}') {
                boolean isSame = isTopSame(ch, stack);
                if (!isSame) {
                    return false;
                }
            } else {
                stack.push(ch);
            } 

        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }

    private boolean isTopSame(char ch, Deque<Character> stack) {
    // 当stack无元素时,pop()方法会抛出NoSuchElementException,若要使用pop()需要先为栈判空,简易起见使用poll()。
        Character top = stack.poll(); 
        if (top == null) {
            return false;
        }
        if (top == '(') {
            top = ')';
        } else if (top == '[') {
            top = ']';
        } else {
            top = '}';
        }
        if (top != ch) {
            return false;
        }
        return true;
    }

三、注意事项

Java中有Stack 类,但是不建议使用,往往用双端队列 ArrayDeque代替栈职能。