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:
        # 第一步，得到删除后的s
        sStack = []
        for ch in s:
            if ch != '#':
                sStack.append(ch)
            elif len(sStack) > 0:
                sStack.pop()
        sNew = ''.join(sStack)
        # 第二步，得到删除后的t
        tStack = []
        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 += 1
                    pointer1 -= 1
                elif delete1 > 0:  # 非#时，判断该字符是否要被删除
                    delete1 -= 1
                    pointer1 -= 1
                else:
                    break
            # 寻找t中用于比较的当前有效字符
            while pointer2 >= 0:
                if t[pointer2] == '#':  # 遇到#
                    delete2 += 1
                    pointer2 -= 1
                elif delete2 > 0:  # 非#时，判断该字符是否要被删除
                    delete2 -= 1
                    pointer2 -= 1
                else:
                    break
            # 比较当前有效字符
            if pointer1 >= 0 and pointer2 >= 0:
                if s[pointer1] != t[pointer2]:
                    return False
                else:
                    pointer1 -= 1
                    pointer2 -= 1
            elif pointer1 < 0 and pointer2 < 0:
                return True
            else:
                return False
        return True


if __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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

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 result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            s = input().strip()[1: -1]
            print(obj.removeDuplicates(s))
        except EOFError:
            break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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 = 0
        for 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)  # 栈为空，相当于上一个不匹配的位置是-1
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            s = input().strip().split('=')[1].strip()[1: -1]
            print(obj.longestValidParentheses(s))
        except EOFError:
            break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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 True
        return False


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            s = input().strip().split('=')[1].strip()[1: -1]
            print(obj.isValid(s))
        except EOFError:
            break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

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 True
        return False


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            s = input().strip().split('=')[1].strip()[1: -1]
            print(obj.isValid(s))
        except EOFError:
            break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

71. 简化路径

1、本题同样是一道字符串相邻元素删除类型的题目，只不过删除的条件没上面几道题目简单了，一开始我顺着题意模拟各种情况做删除，虽然一点点调试通过了，但情况分类有点太多了
2、优化后的思路：以/为分割字符，对/夹着的子串进行判断，栈初始化就把根目录/添加上，然后对有效文件名的子串入栈后，再把/入栈；最后遍历完后，把最后一个路径的/再去掉

'''
71. 简化路径
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
示例 1:
    输入：path = "/home/"
    输出："/home"
    解释：注意，最后一个目录名后面没有斜杠。
题眼：后面的路径符号先被处理—
思路：回退可以看作是相邻元素的删除，而且是先入后出，所以考虑用栈实现，但是比前面几道题要繁琐一些：入栈和出栈的边界情况比较多
优化：以/为分割字符，对/夹着的子串进行判断，栈初始化就把根目录/添加上，然后对有效文件名的子串入栈后，再把/入栈；最后遍历完后，把最后一个路径的/再去掉
'''


class Solution:
    def simplifyPath(self, path: str) -> str:
        # stk = ['/']  # 提前把根目录入栈
        # i = 0
        # while i < len(path):
        #     if path[i] == '/':  # 遇到'/'不处理
        #         i += 1
        #     elif path[i] == '.' and i + 1 < len(path) and path[i + 1] == '/':  # ./表示当前目录
        #         i += 2
        #     elif path[i] == '.' and i + 1 < len(path) and path[i + 1] == '.' and i + 2 == len(path): # 最后刚好是..：要回退，即删除上个路径
        #         if len(stk) >= 3:  # 回退必须满足不止有根目录
        #             stk.pop()
        #             stk.pop()
        #         i += 3
        #     elif path[i] == '.' and i + 1 < len(path) and path[i + 1] == '.' and i + 2 < len(path) and path[i + 2] == '/': # ../表示要回退，即删除上个路径
        #         if len(stk) >= 3:  # 回退必须满足不止有根目录
        #             stk.pop()
        #             stk.pop()
        #         i += 3
        #     elif path[i] == '.' and i == len(path) - 1:
        #         i += 1
        #     else:  # 剩下全都是有效目录名
        #         ans = ""
        #         while i < len(path) and path[i] != '/':
        #             ans += path[i]
        #             i += 1
        #         stk.append(ans)
        #         stk.append('/')
        # if len(stk) > 1:  # 把最后一个路径的/去掉
        #     stk.pop()
        # return ''.join(stk)

        # 尝试优化下：以/为分割字符，对/夹着的子串进行判断
        stk = ['/']  # 提前把根目录入栈
        i = 0
        while i < len(path):
            if path[i] == '/':  # 遇到/不处理
                i += 1
            else:  # 获取/之间的子串，并对子串情况进行判断
                ans = ''
                while i < len(path) and path[i] != '/':
                    ans += path[i]
                    i += 1
                if ans == '.':
                    continue
                elif ans == '..':
                    if len(stk) >= 3:  # 回退必须满足不止有根目录
                        stk.pop()
                        stk.pop()
                else:  # 有效文件名
                    stk.append(ans)
                    stk.append('/')
        if len(stk) > 1:  # 把最后一个路径的/去掉
            stk.pop()
        return ''.join(stk)


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            path = in_line[1].strip()[1: -1]
            print(obj.simplifyPath(path))
        except EOFError:
            break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79