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.


Naive Way:  Use a stack would be straightforward. But it's O(n) space.

 public class Solution {  
   public boolean isValid(String s) {  
     Stack<Integer> stack = new Stack<Integer>();  
     for(int i = 0;i < s.length();i++){  
       if(isLeft(s.charAt(i))) stack.push(i);  
       else if(!stack.isEmpty() && s.charAt(stack.peek())== opposite(s.charAt(i))) stack.pop();  
       else return false;  
     }  
     return stack.isEmpty();  
   }  
   private boolean isLeft(char c){  
     return c=='(' || c=='{' || c =='[';  
   }  
   private char opposite(char c){  
     if(c==')') return '(';  
     if(c=='}') return '{';  
     else return '[';  
   }  
 }  

I know if there were only one type of parentheses, it can be done in O(1). When there are multiple parentheses, some one argue that for the reason of Context Free Grammar, It can not be done in O(1).

Improved Way: It would be better to use a Hashmap to map left parentheses to right parentheses.

 public class Solution {  
   private static final Map<Character, Character> map = new HashMap<Character, Character>(){{  
     put('(',')');  
     put('{','}');  
     put('[',']');  
   }};  
   public boolean isValid(String s) {  
     Stack<Integer> stack = new Stack<Integer>();  
     for(int i = 0;i < s.length();i++){  
       if(map.containsKey(s.charAt(i))) stack.push(i);  
       else if(!stack.isEmpty() && map.get(s.charAt(stack.peek()))==s.charAt(i)) stack.pop();  
       else return false;  
     }  
     return stack.isEmpty();  
   }  
 }