题解 | #有效括号序列#
有效括号序列
http://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2
import java.util.*;
public class Solution {
public boolean isValid (String s) {
// write code here
//方法一 普通方法
int lb = 0,len=s.length();//lb是未匹配的前缀个数
HashSet<Character> set = new HashSet<>();
for(int i=0;i<len;++i){
char c = s.charAt(i);
if(c=='(' ||c=='['||c=='{'){
lb++;
if(!set.contains(c))
set.add(c);
} else if(c==')' ||c==']'||c=='}'){
if(c==')' && (!set.contains('(') || i>0&&(s.charAt(i-1)=='['||s.charAt(i-1)=='{')))
return false;
if(c==']' && (!set.contains('[') || i>0&&(s.charAt(i-1)=='('||s.charAt(i-1)=='{')))
return false;
if(c=='}' && (!set.contains('{') || i>0&&(s.charAt(i-1)=='('||s.charAt(i-1)=='[')))
return false;
if(lb==0)
return false;
lb--;
}
}
if(lb!=0)
return false;
return true;
//方法二 栈
Stack<Character> stk = new Stack<>();
for(int i=0;i<s.length();++i){
char c = s.charAt(i);
if(c=='(' || c=='[' || c=='{')
stk.push(c);
else if(!stk.isEmpty() &&((c==')'&&stk.peek()=='(') || (c==']'&&stk.peek()=='[') || (c=='}'&&stk.peek()=='{'))){
stk.pop();
} else{
return false;
}
}
if(stk.isEmpty())
return true;
return false;
}
}
阿勇算法解集 文章被收录于专栏
对一些基础的,经典的题目的算法题解,每道题的题解尽量做到一题多解,举一反三。其中每一个题解中,若是参考了其他牛人的想法,我会备注出来。