更多精彩内容，请关注【力扣简单题】。

题目

难度：★☆☆☆☆
类型：栈

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

有效字符串需满足：

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

示例

示例 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

如有疑问或建议，欢迎评论区留言~