判断括号是否有效
1.使用栈的先进后出，先把前括号对应的后括号压栈
当后面再遇到后括号的时候，只用比较相等就可以了。
/**
* 时间复杂度O(N) 每个元素都要入栈一遍
*
* @param str
* @return
*/
private static BooleanvalidBracket(String str) {
if (isNullOrEmpty(str)) {
return false;
}
Stack stack =new Stack<>();
for (Character s : str.toCharArray()) {
if (s.equals('(')) {
stack.push(')');
}else if (s.equals('[')) {
stack.push(']');
}else if (s.equals('{')) {
stack.push('}');
}else if (stack.isEmpty()|| !stack.pop().equals(s)) {
return false;
}
}
return stack.isEmpty();
}
另外一种解法：
利用字符串替换，将所有的配对的替换后，结果是是空，即是匹配成功的
/**
* ((([[{{}}]])))
* ((([[{}]])))
* ((([[]])))
* ((([])))
* ((()))
* (())
* ()
* @param s
* @return
*/
private static boolean isValid(String s) {
if (isNullOrEmpty(s)) {
return false;
}
int length;
do {
length = s.length();
s = s.replace("()", "").replace("[]", "").replace("{}", "");
}while (length != s.length());
return s.length() ==0;
}
网友评论