1047. Remove All Adjacent Duplicates In String

模拟栈

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Example 1:

Input: s = "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Example 2:

Input: s = "azxxzy"
Output: "ay"

Constraints:

• 1 <= s.length <= 105

• s consists of lowercase English letters.

分析

栈的应用

1. 使用栈结构来高效地检测和删除相邻重复字符。

2. 遍历字符串 s 的每个字符：

   • 如果栈顶元素与当前字符相同，则弹出栈顶（发现相邻重复）。

   • 否则，将当前字符压入栈中。

3. 遍历结束后，栈中剩下的字符即为最终结果。

如果要求空间复杂度为 O(1)（例如处理极大字符串），可以用双指针模拟栈，直接在原字符串上修改（需转为可变类型如列表）。

• res[slow - 1] 才是“栈顶”元素，因为 slow 指向的是下一个写入位置。

• res[slow] 是未初始化的位置，不能用于比较（否则可能访问越界或错误数据）。

class Solution:
    def removeDuplicates(self, s: str) -> str:
        if not s:
            return s
        res = list(s)
        slow=0
        for fast in range(len(res)):
            if slow > 0 and res[slow-1] == res[fast]:
                slow -= 1
            else:
                res[slow] = res[fast]
                slow += 1
        return ''.join(res[:slow])