Leetcode: 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.

没考虑到的情况有：input: [, expected: false; 语法上也犯了错误：我定义的stack的泛型为char，泛型不能为primitive datatype,

Primitive types such as char cannot be used as type parameters in Java. You need to use the wrapper type:

Stack<Character> stack =newStack<Character>(); 建议有时间再多读读泛型部分

stack做法：（默认方法，用switch）

 1 public boolean isValid(String s) {
 2     if(s==null || s.length()==0)
 3         return true;
 4     LinkedList<Character> stack = new LinkedList<Character>();
 5     for(int i=0;i<s.length();i++)
 6     {
 7         switch(s.charAt(i))
 8         {
 9             case '(':
10             case '{':
11             case '[':
12                 stack.push(s.charAt(i));
13                 break;
14             case ')':
15                 if(stack.isEmpty() || stack.pop()!='(')
16                     return false;
17                 break;
18             case '}':
19                 if(stack.isEmpty() || stack.pop()!='{')
20                     return false;
21                 break;
22             case ']':
23                 if(stack.isEmpty() || stack.pop()!='[')
24                     return false;
25                 break; 
26             default:
27                 break;
28         }
29     }
30     if(stack.isEmpty())
31         return true;
32     return false;
33 }

用数组模拟stack, 用一个head指示栈头的下一个:

 1 public class Solution {
 2     public boolean isValid(String s) {
 3         char[] stack = new char[s.length()];
 4         int head = 0;
 5         for(char c : s.toCharArray()) {
 6             switch(c) {
 7                 case '{':
 8                 case '[':
 9                 case '(':
10                     stack[head++] = c;
11                     break;
12                 case '}':
13                     if(head == 0 || stack[--head] != '{') return false;
14                     break;
15                 case ')':
16                     if(head == 0 || stack[--head] != '(') return false;
17                     break;
18                 case ']':
19                     if(head == 0 || stack[--head] != '[') return false;
20                     break;
21             }
22         }
23         return head == 0;
24 
25     }
26 }