共计 670 个字符,预计需要花费 2 分钟才能阅读完成。
题目
给定一个只包含 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串 s,判断字符串是否无效。
无效字符串需满足:
左括号必须用雷同类型的右括号闭合。
左括号必须以正确的程序闭合。
输出:s = "()"
输入:true
输出:s = "()[]{}"
输入:true
输出:s = "(]"
输入:false
输出:s = "([)]"
输入:false
输出:s = "{[]}"
输入:true
栈
‘()[]’ 和 '([])’ 这两种无效状况,能够看出,只有右括号后面是左括号,它们肯定是一对,能够互相对消的。
利用栈的思维能够很好的解决题目,有种消消乐的感觉。
def isValid(s):
# 如果字符串是奇数,那么必定返回 False
if len(s)%2!=0:
return False
hash = {')':'(',
']':'[',
'}':'{'}
stack = []
for ch in s:
# 如果是右括号
if ch in hash:
# 如果曾经空栈且右括号,间接 False
# 如果栈顶的左括号和以后右括号不配对,间接 False
if not stack or stack[-1]!=hash[ch]:
return False
# 没空栈,且与栈顶左括号配对,则打消这对括号
stack.pop()
else:
# 如果是左括号,间接入栈
stack.append(ch)
# 通过栈的打消,如果是无效括号,应该是空栈
return not stack
工夫复杂度:O(n)
空间复杂度:O(n+∣Σ∣),其中 Σ 示意字符集,本题中字符串只蕴含 6 种括号,∣Σ∣=6。栈中的字符数量为 O(n),而哈希表应用的空间为 O(∣Σ∣),相加即可失去总空间复杂度。
正文完