给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 1:
输入:s = "()" 输出:true
示例 2:
输入:s = "()[]{}" 输出:true
示例 3:
输入:s = "(]" 输出:false
示例 4:
输入:s = "([)]" 输出:false
示例 5:
输入:s = "{[]}" 输出:true
思路:使用栈,先入栈,每当进入一个元素,判断是否和上一个匹配,如果匹配,他们两个出栈,如果括号方法相反,直接返回false,如果括号方向相同,继续下一元素入栈,知道全部都入栈,如果栈不空,返回false
# @lc code=start
class Solution:
def isValid(self, s: str) -> bool:
lens=len(s)
sets={"(":")","{":"}","[":"]"}
left=["(","[","{"]
lists=list()
lists.append(s[0])
j=1
while j<=lens-1:
if lists==[]:
lists.append(s[j])
j=j+1
continue
elif lists[-1] not in left:
print(lists)
return False
elif sets[lists[-1]]==s[j]:
j=j+1
lists.pop()
else:
lists.append(s[j])
j=j+1
print(lists)
return True if lists==[] else False