Valid Parentheses

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.

栈法

复杂度

时间 O(N) 空间 O(N)

思路

栈最典型的应用就是验证配对情况，作为有效的括号，有一个右括号就必定有一个左括号在前面，所以我们可以将左括号都push进栈中，遇到右括号的时候再pop来消掉。这里不用担心连续不同种类左括号的问题，因为有效的括号对最终还是会有紧邻的括号对。如栈中是({[，来一个]变成({，再来一个}，变成(。

注意

栈在peek或者pop操作之前要验证非空，否则会抛出StackEmptyException。

代码

public class Solution {    public boolean isValid(String s) {        Map<Character, Character> map = new HashMap<Character, Character>();        map.put('(',')');        map.put('[',']');        map.put('{','}');        Stack<Character> stk = new Stack<Character>();        for(int i = 0; i < s.length(); i++){Character c = s.charAt(i);switch(c){    case '(': case '[': case '{':        stk.push(c);        break;    case ')': case ']': case '}':        if(stk.isEmpty() || c != map.get(stk.pop())){return false;        }}        }        return stk.isEmpty();    }}