更多精彩内容，请关注【力扣简单题】。
题目
难度：★☆☆☆☆
类型：栈
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解答
方案1：字符串替换
只要遇到一对"()"、"[]"或"{}"，就从字符串中删掉，直到字符串中没有上述重复的括号为止，根据最终是否剩下空串来判断括号是否有效。
class Solution:
def isValid(self, s):
while '{}' in s or '()' in s or '[]' in s:
s = s.replace('{}', '')
s = s.replace('[]', '')
s = s.replace('()', '')
return s == ''
方案2：栈
这里，我们使用栈的数据结构来完成这项任务。准备一个空栈，从头到尾遍历字符串，每当遇到任何左括号时将该括号压入栈，每当遇到右括号时将当前栈顶元素弹出，观察能否与当前右括号匹配，如果不匹配则返回False，遍历结束后如果栈为空则括号有效，否则无效，返回False。
def isValid(self, s):
# 把一个list当做栈使用
ls = []
parentheses = "()[]{}"
for i in range(len(s)):
# 如果不是括号则继续
if parentheses.find(s[i]) == -1:
continue
# 左括号入栈
if s[i] == '(' or s[i] == '[' or s[i] == '{':
ls.append(s[i])
continue
if len(ls) == 0:
return False
# 出栈比较是否匹配
p = ls.pop()
if (p == '(' and s[i] == ')') or (p == '[' and s[i] == ']') or (p == '{' and s[i] == '}'):
continue
else:
return False
if len(ls) > 0:
return False
return True
如有疑问或建议，欢迎评论区留言~
