每日一题:Leetcode20 有效的括号

简介: 每日一题:Leetcode20 有效的括号

题目描述

给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号


示例 1:

输入:s = “()”
输出:true


示例 2:

输入:s = “()[]{}”
输出:true


示例3:

输入:s = “(]”
输出:false


提示:

1 <= s.length <= 10^4

s 仅由括号 ‘()[]{}’ 组成


一、思路

对称匹配问题,非常适合使用栈来解决;

方法选择:通常不使用Stack类来定义栈,使用性能更优的双端队列接口Deque来定义栈,实现类ArrayDeque/LinkedList来进行初始化

Deque<Character> deque = new ArrayDeque<>();
Deque<Character> deque = new LinkedList<>();


有关栈的一些方法:

pop() : 出栈 删除栈顶元素
push(): 入栈 元素压入栈顶
peek(): 查看栈顶元素
isEmpty(): 判断栈是否为空


本文我们使用实现LinkedList类解答;

解题思路:看到题目后很容易想到使用栈来解决问题,但是我们该怎么去着手呢?怎样去通过栈操作来实现匹配呢?

首先是字符串的长度,如果字符串为奇数,则返回false;另一种情况当然是符合题意的偶数段字符串长度,然后分为三种情况,一种是左边符号多( ‘(((}’ ),第二种是右边符号多( ‘()))’ ),第三种是一样多但是括号不匹配( "((]] ).

我们这里通过一个for循环来进行遍历字符串,通过if语句来对三种情况以及其他情况进行判断,if条件判断


举一个例子:每当有一个左括号时,栈里就push()入一个对应的右括号,一次遍历,此时栈内元素为( “)))”)当s.charAt(i) =='}‘时,栈内没对应元素,返回false ;如果是( ‘((()’ ), 当s.charAt(i) ==’)'时,栈内有元素,弹出栈顶元素,栈内元素为( ‘))’) ,此时字符串里没有对应的右括号来匹配,所以返回fasle;如果是 ( ‘()))’ ),此时栈内元素为 ( ‘)’ ),当for循环遍历匹配了一个右括号时,弹出后,栈内没有元素,栈为空,此时还有两个)没有被匹配,所以此时返回false;同时如果当s.charAt(i) != deque.peek() 时,也是返回false,参考代码更容易来理解


二、参考代码

双指针–滑动窗口:

class Solution {
    public boolean isValid(String s) {
// 栈的使用:
//       使用Deque来定义栈 Deque代替使用Stack 性能更优
//       同时可以使用ArrayDeque和LinkedList
// 当字符串长度为奇数的时候,不满足题意,所以直接返回false
        if(s.length() % 2 != 0){
            return false;
        }
// 使用Deque来定义栈 
        Deque<Character> deque = new LinkedList<>();
        char ch;
// 通过for循环一次对字符进行情况匹配
        for(int i =0;i<s.length();i++){
            if(s.charAt(i) == '('){
                deque.push(')');
            }else if(s.charAt(i) == '{'){
                deque.push('}');
            }else if(s.charAt(i) == '['){
                deque.push(']');
 // 当字符在匹配完,此时栈内为空了,则说明右括号多了,则返回false 同时还有右括号和栈顶元素不匹配,同样返回false
            }else if(deque.isEmpty() || s.charAt(i) != deque.peek()){
                return false;
            }else{
 // **这里的else的条件时  s.charAt(i) = deque.peek()情况**,因为已经判断过不相等的情况了 ,这里是三种右括号匹配时的情况判断,           
                deque.pop();
            }
        }
 // 如果都匹配,则栈内元素为空 返回true ,如果情况为:左括号多了 ,栈内元素不为空,此时返回false       
        return deque.isEmpty();
        }
 }

创作不易:感谢您的一键三连!希望对您有所帮助

相关文章
|
1月前
|
存储 C语言 索引
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
|
1月前
leetcode-301:删除无效的括号
leetcode-301:删除无效的括号
24 0
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
|
7天前
|
SQL 算法 数据可视化
LeetCode 题目 32:最长有效括号【python】
LeetCode 题目 32:最长有效括号【python】
|
7天前
|
存储 SQL 算法
LeetCode第22题:生成括号【22/1000 python 递归|动态规划】
LeetCode第22题:生成括号【22/1000 python 递归|动态规划】
|
7天前
|
SQL 算法 数据挖掘
探索有效括号 力扣第20题:从栈到递归的多角度解法 【含图解 python】
探索有效括号 力扣第20题:从栈到递归的多角度解法 【含图解 python】
|
11天前
|
算法 Java C语言
【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)
12 1
LeetCode | 20. 有效的括号
LeetCode | 20. 有效的括号
|
21天前
|
索引
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
20 0