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

主要思想还是盏。

 1 public static boolean isValid(String s) {
 2     HashMap<Character, Character> map = new HashMap<Character, Character>();
 3     map.put('(', ')');
 4     map.put('[', ']');
 5     map.put('{', '}');
 6  
 7     Stack<Character> stack = new Stack<Character>();
 8  
 9     for (int i = 0; i < s.length(); i++) {
10         char curr = s.charAt(i);
11  
12         if (map.keySet().contains(curr)) {
13             stack.push(curr);
14         } else if (map.values().contains(curr)) {
15             if (!stack.empty() && map.get(stack.peek()) == curr) {
16                 stack.pop();
17             } else {
18                 return false;
19             }
20         }
21     }
22  
23     return stack.empty();
24 }

 1 public class S20 {  
 2    
 3     public static void main(String[] args) {  
 4    
 5     }  
 6        
 7     // 用stack来检查  
 8     public boolean isValid(String s) {  
 9         Stack<Character> stack = new Stack<Character>();  
10         for(int i=0; i<s.length(); i++){  
11             char c = s.charAt(i);  
12             // 如果遇到前括号就压入栈  
13             if(c=='(' || c=='[' || c=='{'){  
14                 stack.push(c);  
15             }else if(c==')' || c==']' || c=='}'){       // 遇到后括号就出栈  
16                 if(stack.size() == 0){  //  说明后括号太多了  
17                     return false;  
18                 }  
19                 char cpop = stack.pop();  
20                 if(cpop=='(' && c==')'){  
21                     continue;  
22                 }else if(cpop=='[' && c==']'){  
23                     continue;  
24                 }else if(cpop=='{' && c=='}'){  
25                     continue;  
26                 }  
27                 return false;  
28             }  
29         }  
30         return stack.size()==0;  
31     }  
32    
33 }