LeetCode 1047. Delete all adjacent duplicates in the string

Title address (1047. Delete all adjacent duplicates in the string )

https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/

Title Description

 Give a string of lowercase letters  S, Duplicate deletion selects two adjacent and identical letters , And delete them .

 stay  S  Repeat the delete operation on , Until you can't delete .

 Returns the final string... After all the duplicates have been deleted . The answer is guaranteed to be unique .

 

 Example ：

 Input ："abbaca"
 Output ："ca"
 explain ：
 for example , stay  "abbaca"  in , We can delete  "bb"  Because two letters are adjacent and the same , This is the only duplicate that can be deleted at this time . And then we get the string  "aaca", There is only  "aa"  You can perform a duplicate deletion operation , So the last string is  "ca".


 

 Tips ：

1 <= S.length <= 20000
S  It's only made up of lowercase letters .

Ideas

Implemented in stack mode

Code

• Language support ：Python3

Python3 Code:

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

Complexity analysis

Make n Is array length .

• Time complexity ：$O(n)$
• Spatial complexity ：$O(n)$