leetcode20.有效的括号

题目链接

解题思路: Stack

本题是涉猎栈这种数据结构的最佳实践题目~思路很简单，因为字符串中只涉及到'(',')','[',']','{','}'几种字符，遍历一遍字符串，如果出现'(','[','{' 则push到栈中，如果出现反括号，则pop栈顶与其比较是否相等，最后遍历完字符串，判断栈是否为空，如果栈为空则说明字符串都是匹配的括号对儿。
代码如下：

class Solution {
    public boolean isValid(String s) {
        char[] chs = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i < chs.length;i++){
            if(chs[i] == '(' || chs[i] == '[' || chs[i] == '{'){
                stack.push(chs[i]);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                char c = stack.pop();
                if(chs[i] == ')' && c != '('){
                    return false;
                }
                if(chs[i] == ']' && c != '['){
                    return false;
                }
                if(chs[i] == '}' && c != '{'){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

时间复杂度为O(N),因为额外用到了栈这种数据结构，所以额外空间复杂度为O(N)。
执行结果: