LeetCode20 有效的括号

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

样例

输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

输入: "{[]}"
输出: true

算法分析

数据结构——栈

• 左括号或者是栈为空的时候，入栈
• 右括号，对比，看能否与栈顶的左括号匹配，匹配就pop，下一个，不匹配直接return false

时间复杂度$O(n)$

Java代码

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stk = new Stack<Character>();

        for(int i = 0; i < s.length(); i++){
            char t = s.charAt(i);
            if(stk.isEmpty() || t == '{' || t == '(' || t == '['){
                stk.push(t);
            }else{
                if(stk.peek() == '(' && t == ')') stk.pop();
                else if(stk.peek() == '[' && t == ']') stk.pop();
                else if(stk.peek() == '{' && t == '}') stk.pop();
                else return false;
            }
        }

        return stk.isEmpty();
    }
}