leetcode分类刷题：栈（Stack）（一、字符串相邻元素删除类型）

1、在leetcode分类刷题：基于数组的双指针（一、基于元素移除的O(1)类型）题目中，采用双指针之快慢指针的算法来解决。
2、字符串相邻元素的删除问题，用栈来进行管理，会非常有效；这种题型排在后面的字母会先删除 与 栈先进后出 的思想一致，同时也要关注相邻元素的细节，是个隐含的连续子序列，否则即使思想上与栈一致，位置上不相邻，栈是没法处理的
3、如果考察最长的相邻重复子串的长度问题，按照索引而非元素入栈的方式来写，比如题目：“32. 最长有效括号”；这类题目判断入栈的情况不能太多了，否则代码太复杂了
4、括号匹配、有效的字符串类问题也属于字符串相邻元素删除的一种，是一种隐含式的相邻元素删除。该类题目处理方式与本章总结的题型基本一致，但也有一点细节区别：入栈的情况里没有栈为空这种，只需要对元素进行不断遍历，然后判断入栈或出栈或return等；这种题目也有更简单直观的思路：遍历元素不加判断地全部入栈，不断对后入栈的栈顶连续元素进行匹配性判断，进行出栈或者直接赋值为空的操作

844. 比较含退格的字符串

是一道基本的字符串相邻元素删除题目，完美符合：排在后面的字母会先删除 与 栈先进后出 的思想一致

from typing import List'''
844. 比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1:输入：s = "ab#c", t = "ad#c"输出：true解释：s 和 t 都会变成 "ac"。
题眼：退格字符只会删除位于它之前的字符
思路：从后向前比较
'''class Solution:# 推荐掌握——O(N)空间复杂度的栈管理字符串元素删除问题def backspaceCompare(self, s: str, t: str) -> bool:# 第一步，得到删除后的ssStack = []for ch in s:if ch != '#':sStack.append(ch)elif len(sStack) > 0:sStack.pop()sNew = ''.join(sStack)# 第二步，得到删除后的ttStack = []for ch in t:if ch != '#':tStack.append(ch)elif len(tStack) > 0:tStack.pop()tNew = ''.join(tStack)# 第三步，比较返回后的两个新字符串return sNew == tNew# 不推荐掌握——O(1)空间复杂度的双指针解法：需要额外再使用标志  标记当前待删除的字符的数量def backspaceCompare2(self, s: str, t: str) -> bool:pointer1, pointer2 = len(s) - 1, len(t) - 1  # 标记字符串末尾的位置delete1, delete2 = 0, 0  # 当前待删除的字符的数量：表示从后向前遇到的#数量while pointer1 >= 0 or pointer2 >= 0:# 寻找s中用于比较的当前有效字符while pointer1 >= 0:if s[pointer1] == '#':  # 遇到#delete1 += 1pointer1 -= 1elif delete1 > 0:  # 非#时，判断该字符是否要被删除delete1 -= 1pointer1 -= 1else:break# 寻找t中用于比较的当前有效字符while pointer2 >= 0:if t[pointer2] == '#':  # 遇到#delete2 += 1pointer2 -= 1elif delete2 > 0:  # 非#时，判断该字符是否要被删除delete2 -= 1pointer2 -= 1else:break# 比较当前有效字符if pointer1 >= 0 and pointer2 >= 0:if s[pointer1] != t[pointer2]:return Falseelse:pointer1 -= 1pointer2 -= 1elif pointer1 < 0 and pointer2 < 0:return Trueelse:return Falsereturn Trueif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')s = in_line[1].split(',')[0].strip()[1: -1]t = in_line[2].strip()[1: -1]print(obj.backspaceCompare(s, t))except EOFError:break

1047. 删除字符串中的所有相邻重复项

1、与“844. 比较含退格的字符串”的处理方式基本一致
2、该类型题目还可以用等价地按照索引而非元素入栈的方式来写，这是在考察最长的相邻重复子串的长度问题的解题模板，比如接下来的一道题目：“32. 最长有效括号”

'''
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例 1:
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，
其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
题眼：排在后面的字母会先删除 与 栈先进后出 的思想一致
思路：
'''class Solution:def removeDuplicates(self, s: str) -> str:stk = []for ch in s:if len(stk) == 0 or stk[-1] != ch:  # 入栈情况stk.append(ch)else:  # 出栈情况stk.pop()return ''.join(stk)# # 按照索引入栈的方式写# stk = []# for i in range(len(s)):#     if len(stk) == 0 or s[stk[-1]] != s[i]:  # 入栈情况#         stk.append(i)#     else:  # 出栈情况#         stk.pop()# result = ''# for i in stk:#     result += s[i]# return resultif __name__ == "__main__":obj = Solution()while True:try:s = input().strip()[1: -1]print(obj.removeDuplicates(s))except EOFError:break

32. 最长有效括号

该题按照索引而非元素入栈的方式来写，将遍历元素是不匹配时把索引全部入栈，匹配时进行出栈，并计算此时的有效括号的长度，更新答案

'''
32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1:输入：s = ")()())"输出：4解释：最长有效括号子串是 "()()"
题眼：括号匹配是使用栈解决的经典问题 —— 后遇到的左括号要先闭合
思路：1、这里从字符串里选择 最长的有效括号子串2、因为是求长度，所以需要有标志记录 起始位置，正好把 压入栈的数据 设置为 不匹配的元素的索引3、遇到匹配出栈时，就可以用 遍历元素索引 - 栈顶元素索引 = 当前有效括号序列长度
'''class Solution:def longestValidParentheses(self, s: str) -> int:# 情况1、字符串为空if not s:return 0# 情况2、用栈判断stk = []result = 0for i in range(len(s)):# 入栈的情况：栈为空、当前元素为（、栈顶元素为）——不匹配才需要入栈if len(stk) == 0 or s[i] == '(' or s[stk[-1]] == ')':stk.append(i)  # 压入栈的数据 设置为 不匹配的元素的索引else:  # 匹配出栈stk.pop()if len(stk) > 0:  # 此时依然要判断栈是否为空，因为可能存在上一步出栈，为空了result = max(result, i - stk[-1])else:result = max(result, i + 1)  # 栈为空，相当于上一个不匹配的位置是-1return resultif __name__ == "__main__":obj = Solution()while True:try:s = input().strip().split('=')[1].strip()[1: -1]print(obj.longestValidParentheses(s))except EOFError:break

20. 有效的括号

1、该说不说，这题首先先要把题意弄明白
2、该题有两种思路：思路1、与本章总结题型的大思路一致，充分利用栈的思想，在遍历字符串时遇到左括号按照对应的右括号形式添加（处理技巧），遇到右括号时判断匹配情况；思路2、将栈当作一个特殊格式的存储空间，将元素全部遍历入栈，并总是在栈中去掉成对的括号——更简单直观

'''
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
有效字符串需满足：1、左括号必须用相同类型的右括号闭合。2、左括号必须以正确的顺序闭合。————这个应该是栈的特点3、每个右括号都有一个对应的相同类型的左括号。
示例 1:输入：s = "()"输出：true
题眼：括号匹配是使用栈解决的经典问题 —— 后遇到的左括号要先闭合 与 栈先进后出 的思想一致
思路1、充分利用栈的思想，在遍历字符串时遇到左括号按照对应的右括号形式添加（处理技巧），遇到右括号时判断匹配情况
思路2、将栈当作一个特殊格式的存储空间，将元素全部遍历入栈，并总是在栈中去掉成对的括号——更简单直观
'''class Solution:def isValid(self, s: str) -> bool:# 思路1、充分利用栈的思想，在遍历字符串时遇到左括号按照对应的右括号形式添加，遇到右括号时判断匹配情况# # 情况1、s长度为奇数，# if len(s) % 2 == 1:#     return False# # 情况2、s长度为偶数# stk = []# for ch in s:#     if ch == '(':#         stk.append(')')#     elif ch == '[':#         stk.append(']')#     elif ch == '{':#         stk.append('}')#     else:  # 说明到了右括号了#         if len(stk) == 0:  # 右括号多了#             return False#         elif ch != stk[-1]:  # 左右括号不匹配#             return False#         else:#             stk.pop()  # 元素正常出栈# if len(stk) > 0:#     return False  # 左括号多了# return True# 思路2、将栈当作一个特殊格式的存储空间，将元素全部遍历入栈，并总是在栈中去掉成对的括号——更简单直观stk = []for ch in s:stk.append(ch)if len(stk) >= 2:target = ''.join(stk[-2:])if target == '()' or target == '[]' or target == '{}':stk[-2:] = []if len(stk) == 0:return Truereturn Falseif __name__ == "__main__":obj = Solution()while True:try:s = input().strip().split('=')[1].strip()[1: -1]print(obj.isValid(s))except EOFError:break

1003. 检查替换后的词是否有效

1、这题把题意弄明白也很重要，它和“20. 有效的括号”是一个意思
2、该题也有两种思路：思路1、类似“20. 有效的括号”的思路一，遍历每个元素，分情况讨论入栈、出栈情况；思路2、类似“20. 有效的括号”的思路而，将栈当作一个特殊格式的存储空间，将元素全部遍历入栈，并总是在栈中去掉成对的括号——更简单直观

'''
1003. 检查替换后的词是否有效
给你一个字符串 s ，请你判断它是否 有效 。
字符串 s 有效 需要满足：假设开始有一个空字符串 t = "" ，你可以执行 任意次 下述操作将 t 转换为 s ：
将字符串 "abc" 插入到 t 中的任意位置。形式上，t 变为 tleft + "abc" + tright，其中 t == tleft + tright 。注意，tleft 和 tright 可能为 空 。
如果字符串 s 有效，则返回 true；否则，返回 false。
示例 1:输入：s = "aabcbc"输出：true解释："" -> "abc" -> "aabcbc"因此，"aabcbc" 有效。
题眼：这道题读懂题目很重要，它和“20. 有效的括号”是一个意思
思路1、类似“20. 有效的括号”的思路，遍历每个元素，分情况讨论入栈、出栈情况
思路2、将栈当作一个特殊格式的存储空间，将元素全部遍历入栈，并总是在栈中去掉目标子串——更简单直观
'''class Solution:def isValid(self, s: str) -> bool:# 思路1、类似“20. 有效的括号”的思路# stk = []# for ch in s:#     if ch == 'a':#         stk.append(ch)#     elif ch == 'b':#         if len(stk) == 0:#             return False#         elif stk[-1] == 'a':#             stk.append(ch)#         else:#             return False#     elif ch == 'c':#         if len(stk) == 0:#             return False#         elif stk[-1] == 'b':#             stk.pop()#             stk.pop()#         else:#             return False# if len(stk) == 0:#     return True# return False# 思路2、将栈当作一个特殊格式的存储空间，将元素全部遍历入栈，并总是在栈中去掉子串abc——更简单直观stk = []for ch in s:stk.append(ch)if len(stk) >= 3:target = ''.join(stk[-3:])if target == 'abc':stk[-3:] = []if len(stk) == 0:return Truereturn Falseif __name__ == "__main__":obj = Solution()while True:try:s = input().strip().split('=')[1].strip()[1: -1]print(obj.isValid(s))except EOFError:break

1910. 删除一个字符串中所有出现的给定子字符串

1、这题是上一题"1003. 检查替换后的词是否有效"的一般情况
2、该题不适合"1003. 检查替换后的词是否有效"的思路一了，因为没法加判断条件对入栈出栈分情况处理了；只能用思路二：将栈当作一个特殊格式的存储空间，将元素全部遍历入栈，并总是在栈中去掉成对的括号——更简单直观
3、官方题解还有一种字符串匹配的思路，感觉不如栈的这种方式直观

'''
1910. 删除一个字符串中所有出现的给定子字符串
给你两个字符串 s 和 part ，请你对 s 反复执行以下操作直到 所有 子字符串 part 都被删除：
找到 s 中 最左边 的子字符串 part ，并将它从 s 中删除。
请你返回从 s 中删除所有 part 子字符串以后得到的剩余字符串。
一个 子字符串 是一个字符串中连续的字符序列。
示例 1:输入：s = "daabcbaabcbc", part = "abc"输出："dab"解释：以下操作按顺序执行：- s = "daabcbaabcbc" ，删除下标从 2 开始的 "abc" ，得到 s = "dabaabcbc" 。- s = "dabaabcbc" ，删除下标从 4 开始的 "abc" ，得到 s = "dababc" 。- s = "dababc" ，删除下标从 3 开始的 "abc" ，得到 s = "dab" 。此时 s 中不再含有子字符串 "abc" 。
题眼："1003. 检查替换后的词是否有效"的一般情况
思路、将栈当作一个特殊格式的存储空间，将元素全部遍历入栈，并总是在栈中去掉目标子串——更简单直观
'''class Solution:def removeOccurrences(self, s: str, part: str) -> str:# 情况1、s比part长度短if len(s) < len(part):return s# 情况2、用栈处理stk = []for ch in s:stk.append(ch)if len(stk) >= len(part):target = ''.join(stk[-len(part): ])if target == part:stk[-len(part): ] = []return ''.join(stk)if __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')s = in_line[1].strip().split(',')[0][1: -1]part = in_line[2].strip()[1: -1]print(obj.removeOccurrences(s, part))except EOFError:break