?1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng)
難度：簡(jiǎn)單
給出由小寫字母組成的字符串 S，重復(fù)項(xiàng)刪除操作會(huì)選擇兩個(gè)相鄰且相同的字母，并刪除它們。
在 S 上反復(fù)執(zhí)行重復(fù)項(xiàng)刪除操作，直到無法繼續(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僅由小寫英文字母組成。
??思路：棧
遍歷字符串：
- 當(dāng)前元素與棧頂元素（棧不為空時(shí)）不相等時(shí)就壓入棧；
- 相等時(shí)，彈出棧頂元素；
可以拿字符串直接作為棧，這樣省去了棧還要轉(zhuǎn)為字符串的操作。
??代碼：(Java、C++)
Java
class Solution {
public String removeDuplicates(String s) {
StringBuffer ans = new StringBuffer();
int top = -1;//存儲(chǔ)ans的長(zhǎng)度
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(top > -1 && ans.charAt(top) == c){
ans.deleteCharAt(top);
top--;
}else{
ans.append(c);
top++;
}
}
return ans.toString();
}
}
C++
class Solution {
public:
string removeDuplicates(string s) {
string ans;
for(char c : s){
if(!ans.empty() && ans.back() == c){
ans.pop_back();
}else{
ans.push_back(c);
}
}
return ans;
}
};
?? 運(yùn)行結(jié)果：
?? 復(fù)雜度分析：
-
時(shí)間復(fù)雜度：
O
(
n
)
O(n)
O(n)，其中
n為字符串的長(zhǎng)度，我們只需要遍歷該字符串一次。 - 空間復(fù)雜度： O ( 1 ) O(1) O(1)，返回值不計(jì)空間復(fù)雜度。
題目來源：力扣。文章來源：http://www.zghlxwxcb.cn/news/detail-481693.html
放棄一件事很容易，每天能堅(jiān)持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁(yè) / CSDN—力扣專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-481693.html
注： 如有不足，歡迎指正！
到了這里，關(guān)于(棧和隊(duì)列) 1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng) ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
