LeetCode 20:Valid Parentheses

作者: LiHui 分类: LeetCode 发布时间: 2018-04-12 17:40

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.

 

终于有一道栈的题目了,首先题目看清,containing just,也就是传入的字符串只有这6种字符,括号正常匹配,包括{[]}这种也是合理的

1:凡是括号的左半边( [ {都压栈

2:如果新来的是括号的右半边:

(1)如果stack是空的,没法匹配,返回false

(2)如果stack的栈顶不是匹配的左半边,根据递归的想法,没法匹配,返回false

(3)如果stack的栈顶是匹配的左半边,直接弹出,可以想象成连连看一样,配对了自动消除

假如字符串合理,最终stack里应该都弹出,清空了

Java源码

package com.maoxiaomeng;

import java.util.Stack;

/**
* @author lihui
* @date 2018/3/26 12:31
*/


public class Solution {
public boolean isValid(String s) {
int len = s.length();
if (s == null || len == 0 || len % 2 != 0) {
return false;
}
/**
* ([{}])
*/
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < len; i++) {
char current = s.charAt(i);
if (current == '(' || current == '[' || current == '{') {
stack.push(current);
} else if (current == ')') {
if (stack.isEmpty() || stack.peek() != '(') {
return false;
} else {
stack.pop();
}
} else if (current == ']') {
if (stack.isEmpty() || stack.peek() != '[') {
return false;
} else {
stack.pop();
}
} else if (current == '}') {
if (stack.isEmpty() || stack.peek() != '{') {
return false;
} else {
stack.pop();
}
}
}

return stack.isEmpty();
}
}

这里要注意的是isEmpty的判断和peek()的值,在if里是有先后次序的,一开始我把isEmpty放在||的后面,那么假如字符串第一个字符为)/]/}的时候,这个时候还没有压栈,为空,调用peek()方法就会抛出异常

peek()源码如下

/**
* Looks at the object at the top of this stack without removing it
* from the stack.
*
* @return the object at the top of this stack (the last item
* of the <tt>Vector</tt> object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E peek() {
int len = size();

if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}

必须非空才能调用

纯属恶搞

浙ICP备16024533号

浙公网安备 33010802007459号