leetcode-20-valid-parentheses

Description

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

An input string is valid if:

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

Note that an empty string is also considered valid.

Example 1:

1 2	Input: "()" Output: true

Example 2:

1 2	Input: "()[]{}" Output: true

Example 3:

1 2	Input: "(]" Output: false

Example 4:

1 2	Input: "([)]" Output: false

Example 5:

1 2	Input: "{[]}" Output: true

思路

題意是判斷括號匹配是否正確，很明顯，我們可以用棧來解決這個問題，當出現左括號的時候入棧，當遇到右括號時，判斷棧頂的左括號是否何其匹配即可，最終判斷是否空棧即可。

public boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
        Map<Character,Character> map= new HashMap<>();
             map.put(')','(');
             map.put(']','[');
             map.put('}','{');
        for(char c : s.toCharArray() ){
            if(stack.isEmpty()){
                stack.push(c);
            }else if(stack.isEmpty() || map.get(c)!=stack.pop()){
                return false;
            }
        }

        return stack.isEmpty();
    }