有效的括号

golang中的栈与php标准库内的栈结构,以双向链表结构体(或类)充当容器栈。
但有时面对轻量级问题,可用php中的数组,亦可用golang中的切片来模拟栈,小巧好用。

题面

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

有效字符串需满足:

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

来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/valid-par...

分析

  1. map结构充当配对字符串映射
  2. 切片栈顶元素,与后续比对成则操作出栈,其余依次入栈
  3. 计切片栈长度空,为匹配成功

上码

func isValid(s string) bool {
    m :=make(map[string]string, 3)
    m["("]=")"
    m["{"]="}"
    m["["]="]"
    stack :=[]string{}
    for i:=0;i<len(s);i++{
        if len(stack) >0 {
            if top,ok := m[stack[len(stack)-1]];ok {
                if top == string(s[i]) {
                    stack = stack[:len(stack)-1]
                    continue
                }
            }
        }
        stack=append(stack, string(s[i]))
    }
    if len(stack)>0{
        return false
    }
    return true
}

python

看似代码量少,但性能呵呵

class Solution:
    def isValid(self, s: str) -> bool:
        st = []
        m={k:v for k,v in zip('([{',')]}')}
        for c in s:
            if st and m.get(st[-1],None)==c:
                st.pop()
                continue
            st.append(c)
        if len(st)>0:
            return False
        return True

测评

提交时间 提交结果 运行时间 内存消耗 语言
几秒前 通过 0 ms 2.3 MB Go
几秒前 通过 40 ms 13.5 MB Python3
本作品采用《CC 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
开发者 @ 社科大
文章
133
粉丝
24
喜欢
100
收藏
54
排名:107
访问:8.9 万
私信
所有博文
社区赞助商