20. 有效括号
leetcode题目链接：https://leetcode.cn/problems/valid-parentheses/
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例：
示例1：
输入：s = "()"
输出：true
示例2：
输入：s = "()[]{}"
输出：true
示例3：
输入：s = "(]"
输出：false
题目解读&思考过程：
本题是栈的经典应用，下面是我的思考过程：
首先字符串有效的条件中1、3要求左右括号能够正常匹配，不能有多余的；重点在第二个条件：左括号必须以正确的顺序闭合，这是什么意思呢？可以举一个例子来看看匹配过程；
例如：字符串 s = "{()[()]}"，这就是一个满足条件的字符串，匹配过程如下：
- 遇到左括号不进行匹配，把左括号保存起来；--> 左括号按序用一个数据类型进保存
- 遇到右括号时，对最后保存的一个左括号进行类型匹配；--> 遇到右括号时，匹配最后一个左括号
- 匹配成功后删除对应的左括号 --> 匹配成功后从数据结构中移除对应左括号
整个匹配过程是非常满足栈先进先出的特性的；
Python代码：
class Solution:
def isValid(self, s: str) -> bool:
stack = [] # 定义栈,用于保存左括号对应的右括号
for item in s:
if item == '{': # 匹配左括号-> 入栈 -> 且是对应的右括号
stack.append('}')
elif item == '[':
stack.append(']')
elif item == '(':
stack.append(')')
elif not stack or stack[-1] != item: # 匹配右括号,先判断栈是否非空,再比较值
return False
else: # 匹配成功->最后一个元素->出栈
stack.pop()
return True if not stack else False
1047. 删除字符串中所有相邻重复项
leetcode题目：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
题目描述：
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
题目解读&思考过程：
本题也是经典的栈应用，和20. 有效括号一样都是匹配问题，匹配到后再做消除操作；
Python代码：
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = []
for item in s:
if not stack or item != stack[-1]:
stack.append(item)
else:
stack.pop()
return "".join(stack)
1047. 删除字符串中所有相邻重复项
leetcode题目：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
题目描述：
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
题目解读&思考过程：
本题也是经典的栈应用，和20. 有效括号一样都是匹配问题，匹配到后再做消除操作；
Python代码：
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = []
for item in s:
if not stack or item != stack[-1]:
stack.append(item)
else:
stack.pop()
return "".join(stack)