有效的括号.md

20.有效的括号

题目

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

有效字符串需满足：

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

输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "([)]"
输出: false

分析

方法一：

利用字符串替换的方法，如果该字符串是有效字符串，最终总能被替换为空字符串。

def isValid(s):
    while '()' in s or '[]' in s or '{}' in s:
        s = s.replace('()', '').replace('[]', '').replace('{}', '')
    return not s

方法二：

• 每次遇到左括号，就入栈
• 遇到右括号，如果是有效字符串，此时栈的最后一个元素肯定与该右括号匹配。
• 把已经匹配的字符，从栈中弹出

def isValid(s):
    stack = []
    for char in s:
        if char not in ['(', '{', '[']:
            # 碰到右括号就弹栈
            if not stack:
                return False

            if (stack[-1] + char) not in ('()', '{}', '[]'):
                return False

            stack.pop()
        else:
            # 碰到左括号就入栈
            stack.append(char)

    return not stack