1.15 Valid Parentheses

Description

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.

Method

stack

Time and Space Complexity

o(n)

Code

public class Solution {

   public boolean isValid(String str) {
       if (str == null || str.length() == 0){
           return false;
       }
       Stack<Character> s = new Stack<Character>();
       s.push('.');
       for (int i = 0; i < str.length(); i++){
            char c = str.charAt(i);
            switch(c){
                 case '(':
                 case '{':
                 case '[': s.push(c);
                           break;
                 case '}' :  if (s.peek() != '{'){
                                return false;
                             } else {
                                 s.pop();
                             }
                             break;
                 case ')' :  if (s.peek() != '('){
                                return false;
                             } else {
                                 s.pop();
                             }
                             break;
                case ']' :  if (s.peek() != '['){
                                return false;
                             } else {
                                 s.pop();
                             }
                             break;
                default  : return false;
            }
       }
       return s.size() == 1;

}

}