Valid Parentheses

Problem:

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.

Analysis:
Use stack and hashmap. Stack makes sure there is always "(" in front of ")", otherwise the string is not valid.

看了几天简单的算法看不懂。昨天找到一种笨方法，就是照着打，估计多打几遍就好了。

Solution:

1:  public class Solution {  
2:    public boolean isValid(String s) {  
3:      char[] chars=s.toCharArray();  
4:      HashMap<Character, Character> map=new HashMap<Character,Character>();  
5:      map.put('(', ')');  
6:          map.put('[', ']');  
7:         map.put('{', '}');  
8:         Stack<Character> stack = new Stack<Character>();  
9:         for(Character c: chars)  
10:         {  
11:           if(map.keySet().contains(c))  
12:            stack.push(c);  
13:           else if(map.values().contains(c))  
14:           {  
15:             if(!stack.isEmpty()&&map.get(stack.peek())==c)  
16:               stack.pop();  
17:             else   
18:             return false;  
19:           }  
20:         }  
21:         return stack.isEmpty();  
22:    }  
23:  }