[Leetcode] 20. Valid Parentheses

Question:

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.

My Test Cases：

“[”
“()[]{}”
“([)]{}”
“([]{})”

Solution 1 (wrong): 只想到了对称的情况

public class Solution {
 public boolean isValid(String s) {
 if (s==null || (s.length())%2 !=0) return false;
 int i=0;
 int j=i+1;
 //int mid=(s.length()/2)-1;
 while (i<s.length() && j<s.length()){
 char a = s.charAt(i);
 char b = s.charAt(j);
 if(pair(a,b)==true){
 i=i+2;
 j=i+1;
 }else{
 return false; 
}
}
 return true;
}
public boolean pair(char a, char b){
 if((a=='('&& b==')') || (a=='{'&& b=='}') || (a=='['&& b==']')){
 return true;
 }else return false;
 }
 }

Solution 2 (right): 用到stack就行, 入栈左括号，遇到右括号出栈道并配对，直到栈为空

public class Solution {
public boolean isValid(String s) {
if (s==null || (s.length())%2 !=0) return false;
Stack<Character> tmp = new Stack<Character>();
int n = s.length();

for (int i=0; i<n; i++){
char a = s.charAt(i);
if (a=='('||a=='{'||a=='[') {
tmp.push(a);
}else{
if (tmp.size()==0) return false;
char b = tmp.pop();
if (a==')'){
if (b != '(') return false;
}else if (a=='}'){
if (b != '{') return false;
}else if (a=='['){
if (b != ']') return false;
}
}
}
return tmp.isEmpty();
}
}

感谢前辈的总结，附上解题参考链接：

http://www.cnblogs.com/springfor/p/3869420.html

https://leetcodenotes.wordpress.com/2013/10/01/leetcode-valid-parentheses-%E4%B8%89%E7%A7%8D%E6%8B%AC%E5%8F%B7%E9%85%8D%E5%AF%B9/