20. 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.

解题方法

Deque: Stack implementation (thinking: first in last out /FILO)

offerLast()

pollLast()

peekLast()

public boolean isValid(String s) {
        if(s == null || s.length() == 0){return true;}

        Deque<Character> deque = new ArrayDeque<>();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){
                deque.offerLast(')');
            }else if(s.charAt(i) == '{'){
                deque.offerLast('}');
            }else if(s.charAt(i) == '['){
                deque.offerLast(']');
            }else{
                if(deque.isEmpty() || s.charAt(i) != deque.pollLast()){
                    return false;
                }
            }
        }
        return deque.isEmpty();
    }