原题链接在这里：

题目：

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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

题解：

当遇到'(', '[', '{' 时压栈，当遇到')', ']', '}'时观察stk是否为空，若是空，返回false，若不是，pop()出来的第一个元素是否对应，若不对应, 返回false. 读完整个string若stk不空，返回false。若没问题，返回true。

Time Complexity: O(s.length()). Space: O(s.length()).

AC Java:

1 public class Solution { 2     public boolean isValid(String s) { 3         if(s == null || s.length() == 0){ 4             return true; 5         } 6          7         Stack
     
       stk = new Stack
      
       (); 8         for(char c : s.toCharArray()){ 9             if(c == '('){10                 stk.push(')');11             }else if(c == '['){12                 stk.push(']');13             }else if(c == '{'){14                 stk.push('}');15             }else if(stk.isEmpty() || stk.pop() != c){16                 return false;17             }18         }19         return stk.isEmpty();20     }21 }