Contents

[Golang][Leetcode][Stack & Queue]刷題系列-1047-Remove All Adjacent Duplicates


1047. Remove All Adjacent Duplicates In String


Level : Easy

原題連結 : Click

題目 :

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 :

Note

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”


解題思路 :

  • 這題的觀念可以參考 leetcode20題解 ,他們一樣是利用stack的特性做出兩兩相鄰配對消去

  • 這題就不需要額外做配對用hash table(map),因為他們是遇到相同的做消,所以直接比較就ok了! easy!!


以下是我的解法

  • 假設golang append function 為 O(1),這支程式的time complexity: O(n) , space complexity: O(n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for Remove All Adjacent Duplicates In String.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func removeDuplicates(s string) string {
    
    bArr := []byte(s)
    
    stack := make([]byte,0)
    
    for i := 0; i < len(bArr); i++ {
        
        l := len(stack)
        
        if l > 0 && stack[l-1] == bArr[i] {
            stack = stack[:l-1]
        }else {
            stack = append(stack,bArr[i])
        }
    }
    
    return string(stack) 
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!