LeetCode 1047：刪除字符串中的所有相鄰重復(fù)項(xiàng)

今天來(lái)做字符串消消樂(lè)，當(dāng)然不是那個(gè)消消樂(lè)，是它的弟中弟中弟版，只需要相鄰是重復(fù)的消掉就好了。

話不多說(shuō)，直接肝題！

   LeetCode 1047：刪除字符串中的所有相鄰重復(fù)項(xiàng)

題意

小寫字母組成字符串 S，重復(fù)項(xiàng)刪除操作會(huì)選擇兩個(gè)相鄰且相同的字母，并刪除它們。

在 S 上反復(fù)執(zhí)行重復(fù)項(xiàng)刪除操作，直到無(wú)法繼續(xù)刪除。

示例

輸入：abbaca

輸出：ca

提示

答案保證唯一

1 <= S.length <= 20000

S 僅由小寫英文字母組成

題目解析

水題，難度簡(jiǎn)單。

匹配到相鄰的兩個(gè)元素是相同的就消除，你看有沒(méi)有眼熟，像不像是括號(hào)匹配那道題。

呃，如果你不知道括號(hào)匹配那道題，看下面鏈接咧，我寫過(guò)

棧，你告訴我這個(gè)括號(hào)配不配！

這種類型的題都算是匹配問(wèn)題，只要是匹配問(wèn)題，大家記住，在沒(méi)有思路的時(shí)候，都可以考慮用棧碰一碰。

既然看透了這道題的本質(zhì)，那做法也就呼之欲出了。

維護(hù)一個(gè)棧，從左到右依次掃描字符串，讓當(dāng)前字符和棧頂元素比較：

• 如果相同，證明當(dāng)前兩個(gè)元素相鄰且相同或者由于之前刪除了相同元素導(dǎo)致間接相鄰且相同，此時(shí)棧頂元素出棧，當(dāng)前字符不入棧。

• 如果不同，則當(dāng)前元素入棧。

如此反復(fù)，直至掃描結(jié)束，棧里剩下啥字符就是啥字符。

需要注意的是，刪除兩個(gè)相鄰且相同的字符可能會(huì)產(chǎn)生新的相鄰且相同的字符。

圖解

假設(shè)字符串 S = abbaca

首先初始化棧

# 初始化棧stack = []

根據(jù)“題目解析”中說(shuō)的，如果當(dāng)前元素與棧頂元素不同，則當(dāng)前元素入棧。

所以第 1 步，當(dāng)前元素為 a，棧為空，所以元素 a 入棧。

第 2 步，當(dāng)前元素為 b，此時(shí)棧頂元素為 a，兩者不相等，所以元素 b 入棧。

接下來(lái)第 3 步，當(dāng)前元素為 b，棧頂元素為 b，兩者相等，棧頂元素出棧。

for char in s:     if stack and stack[-1] == char:        stack.pop()

之后第 4 步，當(dāng)前元素為 a，棧頂元素為 a，這就是由于刪除兩個(gè)相鄰且相同的字符，產(chǎn)生了新的相鄰且相同的字符。

最后兩步?jīng)]有相同的，直接入棧，輸出棧內(nèi)元素即可。

在這提醒一下編程語(yǔ)言直接用“?！边@個(gè)結(jié)構(gòu)的，輸出的時(shí)候要反轉(zhuǎn)下字符串。

因?yàn)閺念^到尾只遍歷字符串 S 一次，所以時(shí)間復(fù)雜度為 O(n)。

在這個(gè)過(guò)程中，維護(hù)了一個(gè)額外的棧，所以本解法空間復(fù)雜度為 O(n)。

代碼實(shí)現(xiàn)

Python 代碼實(shí)現(xiàn)

class Solution:    def removeDuplicates(self, s: str) -> str:        # 初始化棧        stack = []
        for char in s:            # 如果"棧不為空"且"棧頂元素和當(dāng)前元素相同"則棧頂元素出棧            if stack and stack[-1] == char:                stack.pop()            # 否則當(dāng)前元素進(jìn)棧            else:                stack.append(char)                # 棧內(nèi)元素拼接成一個(gè)字符串        return ''.join(stack)

Java 代碼實(shí)現(xiàn)

此處直接拿字符串當(dāng)棧，省去了棧要轉(zhuǎn)為字符串的操作。

class Solution {    public String removeDuplicates(String s) {        // 將 res 當(dāng)做棧        StringBuffer res = new StringBuffer();        // top為 res 的長(zhǎng)度        int top = -1;        for (int i = 0; i < s.length(); i++) {            char c = s.charAt(i);            // 當(dāng) top > 0,即棧中有字符時(shí)，當(dāng)前字符如果和棧中字符相等，彈出棧頂字符，同時(shí) top--            if (top >= 0 && res.charAt(top) == c) {                res.deleteCharAt(top);                top--;            // 否則，將該字符 入棧，同時(shí)top++            } else {                res.append(c);                top++;            }        }        return res.toString();    }}

好啦，圖解這道題目長(zhǎng)長(zhǎng)的題到這里就結(jié)束啦。

這道題就很能說(shuō)明問(wèn)題，其實(shí)就是換湯不換藥，穿上個(gè)馬甲也不能裝烏龜。

大家在做題的時(shí)候還是得仔細(xì)琢磨，不能過(guò)去了就是過(guò)去了。

有問(wèn)題，扔到留言區(qū)。

END

最后，歡迎大家加入帥地的知識(shí)星球，星球里有很多熱愛(ài)學(xué)習(xí)的小伙伴，一群人一起學(xué)習(xí)不孤單。

并且你有任何學(xué)習(xí)上的疑問(wèn)，帥地都會(huì)指導(dǎo)你應(yīng)該如何學(xué)習(xí)，根據(jù)你的情況為你量身定制，在星球會(huì)提供如下服務(wù)：