You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

# 1047. 删除字符串中的所有相邻重复项 - Remove All Adjacent Duplicates In String

. 2 min read

【栈】

## Example:

输入："abbaca"



1. 1 <= S.length <= 20000
2. S 仅由小写英文字母组成。

## Analysis

• 若相同则删除栈顶元素且不插入
• 若不相同则插入新元素

## Solution 【栈】 ( 76ms)

class Solution {
public String removeDuplicates(String S) {
/* 只需删除重复项即可，因此可以使用栈实现
* 每次添加时比较是否与栈顶元素相同
*   - 若相同则删除栈顶元素且不插入
*   - 若不相同则插入新元素
* 时间复杂度：O(N)
* 空间复杂度：O(N)
*/
char[] s = S.toCharArray();
int len = s.length;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < len; i++) {
if (stack.isEmpty() || s[i] != stack.peek()) {
stack.push(s[i]);
} else {
stack.pop();
}
}
/* 数据的展示可以继续优化 */
StringBuilder str = new StringBuilder();
for (Character c : stack) {
str.append(c);
}
return str.toString();

}
}