1047. 删除字符串中的所有相邻重复项
题目描述
输入只含小写字母的字符串 s。
一次操作可以选出两个紧挨着且相同的字母，把它们一起删掉。删除后两侧的字符会接在一起，可能产生新的相邻相同字母。
一直操作到无法再删为止，返回此时的字符串。题目保证结果唯一。
示例 1
输入：s = "abbaca" 输出："ca"
解释：先删 bb 得到 aaca，再删 aa 得到 ca。
示例 2
输入：s = "azxxzy" 输出："ay"
解释：先删 xx 得到 azzy，再删 zz 得到 ay。
数据范围
1 <= s.length <= 10^5s只含小写英文字母。
解题思路
用栈保存“已经稳定”的结果。从左到右读字符，如果它和栈顶相同，说明两者在删除中间部分后相邻，一起消掉（弹栈）；否则压入栈。删除一对后，新的栈顶又可能和下一个字符配对，栈自然处理了这种连锁消除。
为什么正确
栈中从底到顶是已扫描前缀完全消除后的结果，栈中任意相邻两个字符都不相同。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
只扫一遍、和原串的前一个字符 s[i-1] 比较是错的：删除后新的相邻关系只存在于结果里，必须和栈顶比较。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = []
for c in s:
if stack and stack[-1] == c:
stack.pop()
else:
stack.append(c)
return ''.join(stack)class Solution {
public String removeDuplicates(String s) {
StringBuilder stack = new StringBuilder();
for (char c : s.toCharArray()) {
if (stack.length() > 0 && stack.charAt(stack.length() - 1) == c) {
stack.deleteCharAt(stack.length() - 1);
} else {
stack.append(c);
}
}
return stack.toString();
}
}class Solution {
public:
string removeDuplicates(string s) {
string stack;
for (char c : s) {
if (!stack.empty() && stack.back() == c) {
stack.pop_back();
} else {
stack.push_back(c);
}
}
return stack;
}
};func removeDuplicates(s string) string {
stack := []byte{}
for i := 0; i < len(s); i++ {
c := s[i]
if len(stack) > 0 && stack[len(stack)-1] == c {
stack = stack[:len(stack)-1]
} else {
stack = append(stack, c)
}
}
return string(stack)
}var removeDuplicates = function(s) {
const stack = [];
for (const c of s) {
if (stack.length && stack[stack.length - 1] === c) {
stack.pop();
} else {
stack.push(c);
}
}
return stack.join('');
};function removeDuplicates(s: string): string {
const stack: string[] = [];
for (const c of s) {
if (stack.length && stack[stack.length - 1] === c) {
stack.pop();
} else {
stack.push(c);
}
}
return stack.join('');
}