[Python知识库]删除字符串中的所有相邻重复项python(leetcode1047)

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

直接看例子，应该还需注意字符串S?仅由小写英文字母组成。

输入："abbaca"
输出："ca"

先删除bb,后剩aaca，再删除aa，剩ca为输出

1 栈

class Solution(object):
    def removeDuplicates(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []

        # 以下注释的写法存在问题
        # 对第一个字符的处理问题，应该保证第一个元素一定进去stack
        # 以下注释的写法导致对空栈进行pop
        # for i in s:
        #     if stack and stack[-1] != i:
        #         stack.append(i)
        #     else:
        #         # stack需要pop
        #         stack.pop()

        for i in s:
            if stack and stack[-1] == i:
                stack.pop()
            else:
                # stack需要pop
                stack.append(i)
        # return stack 不能直接return stack,输出应该是字符串
        # 拿字符串直接作为栈，省去了栈还要转为字符串的操作。
        # stack是列表实现的，可用join实现字符串否则应该先将stack中元素pop后再反转顺序输出
        return ''.join(stack) 

2 双指针

本质是使用双指针实现了类似栈的操作

class Solution:
    def removeDuplicates(self, s: str) -> str:
        # 使用双指针模拟栈
        slow, fast = 0, 0
        res = list(s)
        while fast < len(s):
            # fast遍历s
            res[slow] = res[fast]
            # slow指针模拟栈中的元素
            if slow > 0 and res[slow] == res[slow - 1]:
                slow -= 1
            else:
                slow += 1
            fast += 1
        return ''.join(res[0 : slow])