Leetcode 20 有效的括号 ( Valid Parentheses *Easy* ) 题解分析

题目介绍

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

示例

Example 1:

Input: s = “()”
Output: true

Example 2:

Input: s = “()[]{}”
Output: true

Example 3:

Input: s = “(]”
Output: false

Constraints:

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'.

解析

easy题,并且看起来也是比较简单的,三种括号按对匹配,直接用栈来做,栈里面存的是括号的类型,如果是左括号,就放入栈中,如果是右括号,就把栈顶的元素弹出,如果弹出的元素不是左括号,就返回false,如果弹出的元素是左括号,就继续往下走,如果遍历完了,如果栈里面还有元素,就返回false,如果遍历完了,如果栈里面没有元素,就返回true

代码

class Solution {
    public boolean isValid(String s) {

        if (s.length() % 2 != 0) {
            return false;
        }
        Stack<String> stk = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '{' || s.charAt(i) == '(' || s.charAt(i) == '[') {
                stk.push(String.valueOf(s.charAt(i)));
                continue;
            }
            if (s.charAt(i) == '}') {
                if (stk.isEmpty()) {
                    return false;
                }
                String cur = stk.peek();
                if (cur.charAt(0) != '{') {
                    return false;
                } else {
                    stk.pop();
                }
                continue;
            }
            if (s.charAt(i) == ']') {
                if (stk.isEmpty()) {
                    return false;
                }
                String cur = stk.peek();
                if (cur.charAt(0) != '[') {
                    return false;
                } else {
                    stk.pop();
                }
                continue;
            }
            if (s.charAt(i) == ')') {
                if (stk.isEmpty()) {
                    return false;
                }
                String cur = stk.peek();
                if (cur.charAt(0) != '(') {
                    return false;
                } else {
                    stk.pop();
                }
                continue;
            }

        }
        return stk.size() == 0;
    }
}