python-leetcode 68.有效的括号

题目：

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

有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合，每个右括号都有一个对应相同类型的左括号

---

根据栈这种数据结构。栈的特点是后进后出，即最后放入的元素会被最先取出，这与括号的闭合顺序是吻合的。

具体步骤如下：

1：初始化一个空栈

2：遍历字符串中的每一个字符：

如果遇到左括号，将其压入栈中。

如果遇到右括号，检查栈顶的元素是否是对应的左括号。如果是，弹出栈顶元素，表示括号匹配成功。如果不是，或者栈为空，即没有对应的左括号，则字符串无效

3：遍历结束后，检查栈是否为空：如果栈为空，说明所有括号都正确闭合，字符串有效。如果栈不为空，说明有未闭合的左括号，字符串无效。

class Solution(object):def isValid(self, s):""":type s: str:rtype: bool"""if len(s)%2 !=0:return Falsestack=[]mapping={")":"(","}":"{","]":"["}for char in s:if char in mapping.values():stack.append(char)else:if not stack or stack.pop()!=mapping[char]:return Falsereturn not stack

时间复杂度：O(n) n是字符串的长度，每个字符的入栈和出栈操作都是O(1)

KO空间复杂度：O(n)