本系列为每日算法,主要借助@代码随想录与LeetCode网站的解析,仅做记录与鞭策使用。
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
提示:
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这是一个很有趣的题目,括号的左右必须对等,依次出现,其中会有三种不同情况。
第一种,左侧括号多于右侧。
第二种,两侧相等。
第三种,右侧多于左侧。
可以使用一个容器,每次有一种左侧括号被遍历到,就在容器中放入一个对应的右侧括号,每检测到一个右侧括号,就从容器中取出第一个右侧括号进行判断,如果此时容器为空,或容器中右侧括号不等于遍历到的括号,证明并不等价,这就无法将之抵消,返回错误,其余情况下,只需要从容器中移除即可。
- class Solution {
- public boolean isValid(String s) {
- ArrayDeque
queue = new ArrayDeque<>(); - char[] array = s.toCharArray();
- for (char c : array) {
- String item = String.valueOf(c);
- if (item.equals("(")) {
- queue.offerFirst(")");
- } else if (item.equals("{")) {
- queue.offerFirst("}");
- } else if (item.equals("[")) {
- queue.offerFirst("]");
- } else if (queue.isEmpty() || !item.equals(queue.element())) {
- return false;
- } else {
- queue.remove();
- }
- }
- return queue.isEmpty();
- }
- }