一、题目大意
标签: 栈和队列
https://leetcode.cn/problems/valid-parentheses
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
示例 1:
输入:s = "()"输出:true
示例 2:
输入:s = "()[]{}"输出:true
示例 3:
输入:s = "(]"输出:false
示例 4:
输入:s = "([)]"输出:false
示例 5:
输入:s = "{[]}"输出:true
提示:
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
二、解题思路
思路:括号匹配是典型的使用栈来解决的问题。从左向右遍历,每当遇到左括号便放入栈内,遇到右括号则判断其和栈顶的括号是否是统一类型,是则从栈内取出左括号,否则说明字符不串不合法。
实现:遍历字符串,如果栈为空则将当前字符入栈,如果栈顶字符与当前字符匹配则栈顶字符出栈,不匹配当前字符入栈,遍历结束如果栈为空说明字符串合法。
三、解题方法
3.1 Java 实现
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (Character c : s.toCharArray()) {
if (isPush(stack, c)) {
stack.push(c);
} else {
stack.pop();
}
}
return stack.isEmpty();
}
private boolean isPush(Stack<Character> stack, Character c) {
if (stack.isEmpty()) {
return true;
}
// {[(
boolean isPop = (stack.peek().equals('[') && c.equals(']') ||
stack.peek().equals('{') && c.equals('}') ||
stack.peek().equals('(') && c.equals(')'));
return !isPop;
}
}
复制代码
3.2 2014 年的实现
public class Solution {
public boolean isValid(String s) {
if (s == null || s.length() == 0) {
return true;
}
Stack<Byte> ps = new Stack<Byte>();
byte[] bArr = s.getBytes();
boolean isValid = true;
for (byte b : bArr) {
if (!isValid) {
break;
}
switch (b) {
case '(':
case '[':
case '{':
ps.push(b);
break;
case ')':
case ']':
case '}':
if (!ps.empty()) {
byte tmpB = ps.pop();
if (tmpB == 40) {
tmpB++;
} else {
tmpB+=2;
}
if (tmpB != b) {
isValid = false;
}
} else {
isValid = false;
}
break;
default:
// do nothing
}
}
if (!ps.empty()) {
isValid = false;
}
return isValid;
}
}
复制代码
四、总结小记
评论