leetcode 20 有效的括号——栈
一、题目描述
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1:
输入:s = “()”
输出:true
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses
二、解题思路与代码
这是一道简单题,初看题目想了几种方法:双指针、递归、动态规划,但是都无从下手,最后瞟了眼题解,嘿嘿。思想还是很简单的,用栈先进先出的特性来解题,思路如下:
1.遍历字符串,将所有左括号入栈,遇到右括号时将栈顶元素弹出,判断是否匹配,若不匹配则返回false,匹配则继续遍历。
2.遍历完成后判断栈是否为空,不为空则表明没有完全匹配,返回false。
注意,遍历前可以先将奇数长度的字符串排除。
public boolean isValid(String s) {
if (s == null) {
return false;
}
if (s.length() % 2 != 0) {
return false;
}
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == ')' || ch == ']' || ch == '}') {
boolean isSame = isTopSame(ch, stack);
if (!isSame) {
return false;
}
} else {
stack.push(ch);
}
}
if (!stack.isEmpty()) {
return false;
}
return true;
}
private boolean isTopSame(char ch, Deque<Character> stack) {
// 当stack无元素时,pop()方法会抛出NoSuchElementException,若要使用pop()需要先为栈判空,简易起见使用poll()。
Character top = stack.poll();
if (top == null) {
return false;
}
if (top == '(') {
top = ')';
} else if (top == '[') {
top = ']';
} else {
top = '}';
}
if (top != ch) {
return false;
}
return true;
}
三、注意事项
Java中有Stack 类,但是不建议使用,往往用双端队列 ArrayDeque代替栈职能。