有效的括号
golang中的栈与php标准库内的栈结构,以双向链表结构体(或类)充当容器栈。
但有时面对轻量级问题,可用php中的数组,亦可用golang中的切片来模拟栈,小巧好用。
题面
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/valid-par...
分析
- 用
map
结构充当配对字符串映射 - 切片栈顶元素,与后续比对成则操作出栈,其余依次入栈
- 计切片栈长度空,为匹配成功
上码
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
测评
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: