20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
给定一个字符串，字符串中包含各种括号。判断输入的字符串是否符合规定

An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
规定有：1.括号有开既有合。2.括号开合顺序需要一样。
Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "()[]{}"
Output: true

Example 3:
Input: s = "(]"
Output: false

Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

题目思考

终于遇到一个简单题了
这题很明显用list栈，先如后出原则。但是出的时候需要判断是否符合顺序。
问题就是怎么判断这个顺序是否对的。
可以用两个队列，第一个队列先进，第二个队列将第一个队列出的往里面进，如果第一个队列最上面和第二个队列最上面的的都一样，则一起出。否则将其从第一个移到第二个里面。
至于如何比较是否是成对的。由于已知字符串里面只有括号。所以我们可以通过ascii表进行比较。查询可得，成对的括号之间的差值为1或2。

class Solution:
    def isValid(self, s: str) -> bool:
        l1 = []
        l2 = []
        for i in range(len(s)):
            l1.append(s[i])
       
        for i in range(len(s)):
            tmp1 = l1.pop()
            if len(l2)==0:
                l2.append(tmp1)
            else:
                tmp2 = l2.pop()
                tmp3 = ord(tmp2)-ord(tmp1)
                if tmp3!=1 and tmp3!=2:
                    l2.append(tmp2)
                    l2.append(tmp1)
        if len(l2)==0:
            return True
        else:
            return False
        

答案解析

栈

和我一样的思路，但是我忘记了可以用下标-1表示最后一个。

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        
        pairs = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = list()
        for ch in s:
            if ch in pairs:
                if not stack or stack[-1] != pairs[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)
        
        return not stack

从代码上可以看到这边判断是否符合成对的标准，是通过预先设置字典来实现的。
他还在一开始设置了如果不是二的倍数就直接返回False的方法，这样可以部分时间。

总结

这题还是比较简单的，但是这种题目还是需要注意细节。不然实现起来也是会存在很多问题。