#16_力扣打卡第16天(20）

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
 

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true
 

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
 

class Solution:
    def isValid(self, s: str) -> bool:
        lef=['(','[','{']
        rig=[')',']','}']
        dic={'(':')','[':']','{':'}'}
        stack=list()
        p=0
        if not s:
            return True
        while p<len(s):
            c=s[p]
            p+=1
            if c in lef:
                stack.append(c)
            elif c in rig:
                if stack:
                    if c==dic[stack.pop()]:
                        continue
                    else: 
                        return False
                else:
                    return False
            else:
                continue
        if not stack:
            return True
        return False

思路：

一看到这道题，就明白是关于堆栈的使用，即每次看到一个左括号就入栈，看到一个右括号就出栈，看出栈的括号是否对应，即小括号对应小括号，中括号对应中括号，以此类推，若有一个不符合要求，就直接return false，否则才为真。

然后，看到万能的评论区，这个代码震惊我一百年了属于是。

class Solution:
    def isValid(self, s: str) -> bool:
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''

我居然傻傻地使用堆栈，这才是最简洁的答案，思路巧妙的一个解法。

一个好的思路，远比按部就班顺着出题人的思路好用。