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的方法，这样可以部分时间。
总结
这题还是比较简单的，但是这种题目还是需要注意细节。不然实现起来也是会存在很多问题。
