题目描述
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 2:
输入: “()[]{}”
输出: true
示例 3:
输入: “(]”
输出: false
示例 4:
输入: “([)]”
输出: false
示例 5:
输入: “{[]}”
输出: true
思路分析
本题可以利用栈的特性,即先进后出。
- 遍历整个字符串逐个入栈,
- 比较入栈元素与栈顶元素关系
- 最终,栈如果为空则说明可以匹配返回 true,反之返回 false
参考代码
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
char[] charArr = s.toCharArray();
for (int i = 0; i < charArr.length; i++) {
if (stack.empty() || !checkPair(stack.peek(), charArr[i])) {
stack.push(charArr[i]);
} else {
stack.pop();
}
}
if (stack.empty()) {
return true;
} else {
return false;
}
}
private boolean checkPair(Character c1, Character c2) {
if (c1 == '(' && c2 == ')') {
return true;
}
if (c1 == '{' && c2 == '}') {
return true;
}
if (c1 == '[' && c2 == ']') {
return true;
}
return false;
}
}
可以通过以下网站测试
力扣有效括号
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)