欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

5、有效的括号-Python-LeetCode-20

程序员文章站 2023-12-27 07:58:15
题目给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例 1:输入: "()"输出: true示例 2:输入: "()[]{}"输出: true示例 3:输入: "(]"输出: false示例 4:输入: "([)]"输出: false示例 5:输入: "{[]}"输出: true解法这题有想到碰...

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

有效字符串需满足:

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

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

解法
这题有想到碰到闭括号,判断上一个开括号是不是配对的,但一开始没想到用栈(后进先出的特点),废了点时间;现在讲下用到栈后的主要思路,配对的话用字典就行了:
(1)碰到开括号,就将它放入栈中,稍后再处理
(2)碰到闭括号,就推出并判断栈顶的元素,如果栈顶无元素或者栈顶的开括号与闭括号不匹配,则表达式无效
(3)判断完所有元素后,如果栈为空,则元素全部匹配,表达式有效,反之无效
代码如下:

class Solution(object):
    def isValid(self, s):
        stack = []
        map = {'(': ')', '{': '}', '[': ']'}
        for item in s:
            if item in map:
                stack.append(item)
            else:
                if item in map.values():
                     if stack:
                         tmp = stack.pop()
                     else:
                         return False
                     if map[tmp] != item:
                         return False
        return not stack

该算法主要和s的长度有关,其余栈的操作时间复杂度为O(1),一层循环所以时间复杂度为O(n)
奥利给!
5、有效的括号-Python-LeetCode-20

本文地址:https://blog.csdn.net/weixin_43927540/article/details/107359971

上一篇:

下一篇: