每日一道算法之--有效的括号

栈数组

Word count: 472Reading time: 1 min

 2020/03/03   Share

有效的括号

力扣第20题 : https://leetcode-cn.com/problems/valid-parentheses/

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true

示例 2:

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

示例 3:

输入: “(]”
输出: false

题目分析

题目不难理解,就是括号要一一对应,换句话来说,只要出现了右括号,name就必定有一个左括号与之对应,而且左括号和右括号必须是对称的,刚好栈这种数据结构可以很好地实现这一目的.

要想一一对应,字符串长度必须是偶数
遍历这个数组,每当遇到左括号时,直接入栈
当遇到有括号时,就取出栈顶元素,然后与该括号配对,若配对失败,则证明字符串无效,若配对成功,则继续遍历
直到数组遍历完成并且栈里没有元素以后,则证明字符串有效

翻译成代码如下:

class Solution:
    def isValid(self, s: str) -> bool:
        has_map = {')':'(', '}':'{', ']':'['}
        stack = []
        if len(s) % 2 != 0: return False
        for char in s:
            if char in has_map:
                top_ele = stack.pop() if stack else ''
                if top_ele != has_map[char]: return False
            else:
                stack.append(char)
        return not stack

复杂度分析

时间复杂度：因为我们一次只遍历给定的字符串中的一个字符并在栈上进行 O(1) 的推入和弹出操作,所以时间复杂度为O(n)。

空间复杂度：在最糟糕的情况下，我们最终要把所有括号推到栈上。例如 ((((((((((, 而如果是有效字符串,则也要将n/2的括号入栈,所以空间复杂度为O(n)。

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/03/03/algorithm-20/

发表日期：March 3rd 2020, 7:41:23 pm

更新日期：March 3rd 2020, 7:42:43 pm

Next Post

python的垃圾回收机制
Previous Post

每日一道算法之--二叉树的层次遍历

CATALOG

1. 有效的括号
1. 1.0.0.1. 题目分析
1.0.1. 复杂度分析

