LeetCode刷题之20题有效的括号

发表于 | 更新于 | 分类于
本文字数： 1k | 阅读时长 ≈ 1 分钟

LeetCode刷题之20题有效的括号

难度：简单 思路：栈

一、题目描述

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例：

1
2
输入: "{[]}"
输出: true

二、问题分析

这是一题难度为简单的题，但我仍旧很久没有思路，就是没有想到利用栈的特性，本题是一道经典的栈的特性的题目，想到栈，就成功了一大半。

三、 代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def isValid(self, s):
    res = True
    stack = []
        
    for element in s:
        if not stack: # 栈为空
            stack.append(element) 
            # 利用栈的先进后出的特点，判断列表的尾部即栈的头部的元素情况
        elif stack[-1] == '(' and element == ')':
            stack.pop() # 出栈在栈的头部
        elif stack[-1] == '[' and element == ']':
            stack.pop()
        elif stack[-1] == '{' and element == '}':
            stack.pop()
        else:
            stack.append(element) # 进栈也在栈的头部

        # 判断栈是否为空，为空则说明括号是对称有效
        if stack :
            res = False
        else :
            res = True
            
        return res

复杂度分析：

O(N) N为字符串的长度