目录
内容目录
题目：
Given a string 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.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
解题思路
要实现配对，考虑使用栈。
代码实现
class Solution:
def isValid(self, s: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for chr in s:
if chr in mapping:
top_element = stack.pop() if stack else '#'
if mapping[chr] != top_element:
return False
else:
stack.append(chr)
return not stack
时空分析
时间复杂度 : 对每个元素需要执行push 或pop操作 ，为O(N)
空间复杂度：考虑最坏情况，所有元素都要push,那么是O(N)
