[leetcode]Valid Parentheses

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.

算法思路：

很经典的栈问题，我采用了大量的数据结构，以保证

代码如下：

 1 public class Solution {
 2     public boolean isValid(String s) {
 3         if(s == null || (s.length() & 1 )== 1) return false;
 4         Set<Character> leftSet = new HashSet<Character>();
 5         Set<Character> rightSet = new HashSet<Character>();
 6         char[] left = {'(','[','{'};
 7         char[] right = {')',']','}'};
 8         Map<Character,Character> pair = new HashMap<Character,Character>();
 9         for(int i = 0; i < left.length;leftSet.add(left[i]),pair.put(left[i], right[i++]));
10         for(int i = 0; i < right.length;rightSet.add(right[i++]));
11         Stack<Character> stack = new Stack<Character>();
12         for(int i = 0; i < s.length(); i++){
13             char c = s.charAt(i);
14             if(leftSet.contains(c)) {
15                 stack.push(c);
16             }else if(rightSet.contains(c)){
17                 if(stack.isEmpty() || c != pair.get(stack.pop()) ) return false; 
18             }
19         }
20          return stack.isEmpty();
21     }
22 }

其实完全木有必要，但是我学的数据结构还是多用比较好