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

Leetcode Link: 1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

题目

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一

解法一

思路： 用栈来做

题解：

class Solution:
    def removeDuplicates(self, s: str) -> str:
        if s == "":
            return ""
        stack = collections.deque()
        stack.append(s[0])
        for i in range(1, len(s)):
            if len(stack) != 0 and stack[-1] == s[i]:
                stack.pop()
            elif len(stack) != 0 and stack[-1] != s[i]:
                stack.append(s[i])
            else:
                stack.append(s[i])
        new = []
        while(len(stack)!=0):
            new.append(stack.popleft())
        return "".join(new)

代码精简

class Solution:
    def removeDuplicates(self, s: str) -> str:
	    # 特例精简没了
        stack = collections.deque()
        stack.append(s[0])
        for i in range(1, len(s)):
            if stack and stack[-1] == s[i]: # 判断精简
                stack.pop()
            else:
                stack.append(s[i])
        return "".join(stack)  # 可以直接用

启发和联系

• 判断deque是否为空:if stack，为空返回False，不为空返回True
  • collections.deque可以直接类似list，实现"".join()