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

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

在完成所有重復(fù)項(xiàng)刪除操作后返回最終的字符串。答案保證唯一。

?

示例：

輸入："abbaca"

輸出："ca"

解釋：

例如，在 "abbaca" 中，我們可以刪除 "bb" 由于兩字母相鄰且相同，這是此時(shí)唯一可以執(zhí)行刪除操作的重復(fù)項(xiàng)。之后我們得到字符串 "aaca"，其中又只有 "aa" 可以執(zhí)行重復(fù)項(xiàng)刪除操作，所以最后的字符串為 "ca"。

?

提示：

1 <= S.length <= 20000

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

來(lái)源：力扣（LeetCode）

鏈接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

匹配問(wèn)題一般都用棧解決：

第一種對(duì)法：

class?Solution?{

public:

????string?removeDuplicates(string?s)?{

????????stack<char>?box;

????????stack<char>?ans;

????????for(int?i=0;i<s.size();i++){

????????????if(!box.empty()&&s[i]==box.top())box.pop();

????????????else?box.push(s[i]);

????????}

????????while(!box.empty()){

????????????ans.push(box.top());

????????????box.pop();

????????}

????????string?res;

????????while(!ans.empty()){

????????????res?+=?ans.top();

????????????ans.pop();

????????}

????????return?res;

????}

};

使用了兩個(gè)棧

第二種對(duì)法：

class?Solution?{

public:

????string?removeDuplicates(string?s)?{

????????stack<char>?box;

????????for(int?i=0;i<s.size();i++){

????????????if(!box.empty()&&s[i]==box.top())box.pop();

????????????else?box.push(s[i]);

????????}

????????string?res;

????????while(!box.empty()){

????????????res?+=?box.top();

????????????box.pop();

????????}

????????reverse(res.begin(),res.end());

????????return?res;

????}

};

使用了reverse函數(shù)反轉(zhuǎn)字符串，

注意要將判斷是否為空棧的條件語(yǔ)句放在前面，這樣就不會(huì)出現(xiàn)異常