刪除字串中的所有相鄰重複項

語言: CN / TW / HK
給出由小寫字母組成的字串 S ,重複項刪除操作 會選擇兩個相鄰且相同的字母,並刪除它們。在 S 上反覆執行重複項刪除操作,直到無法繼續刪除。

刪除字串中的所有相鄰重複項刪除字串中的所有相鄰重複項

在完成所有重複項刪除操作後返回最終的字串。答案保證唯一。

示例:

輸入:"abbaca" 
輸出:"ca" 
解釋: 
例如,在 "abbaca" 中,我們可以刪除 "bb" 由於兩字母相鄰且相同,這是此時唯一可以執行刪除操作的重複項。之後我們得到字串 "aaca",其中又只有 "aa" 可以執行重複項刪除操作,所以最後的字串為 "ca"。

提示:

<= S.length <= 20000

S 僅由小寫英文字母組成。

解法:利用棧

解題思路: 遍歷字串,依次入棧,入棧時判斷與棧頭元素是否一致,如果一致,即這兩個元素相同相鄰,則需要將棧頭元素出棧,並且當前元素也無需入棧

解題步驟: 遍歷字串,取出棧頭字元,判斷當前字元與棧頭字元是否一致

不一致,棧頭字元進棧,當前字元進棧

一致,即棧頭字元與當前字元相同相鄰,都不需要進棧,直接進入下次遍歷即可

遍歷完成後,返回棧中字串

程式碼實現:

const removeDuplicates = function(S) { 
    let stack = [] 
    for(c of S) { 
        let prev = stack.pop() 
        if(prev !== c) { 
            stack.push(prev) 
            stack.push(c) 
        } 
    } 
    return stack.join('') 
};

時間複雜度:O(n)

空間複雜度:O(n

本文地址:https://www.linuxprobe.com/adjacent-duplicates-string.html