目录
力扣1047. 删除字符串中的所有相邻重复项
难度 简单
给出由小写字母组成的字符串 S
,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例:
输入:"abbaca" 输出:"ca" 解释: 例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
提示:
1 <= S.length <= 20000
S
仅由小写英文字母组成。
class Solution {
public:
string removeDuplicates(string s) {
}
};
解析代码
本题很像消消乐游戏,仔细观察消除过程,可以发现本题与之前做过的括号匹配问题是类似的。当前元素是否被消除,需要知道上一个元素的信息,因此可以用栈来保存信息。 但是如果使用 stack 容器来保存的话,最后还需要把结果从栈中取出来。不如直接用字符数组模拟一个栈结构:在数组的尾部尾插尾删,实现栈的进栈和出栈。最后数组存留的内容, 就是最后的结果。
class Solution {
public:
string removeDuplicates(string s) {
string stack = "";
for(auto& e : s)
{
if(stack.size() == 0 || stack.back() != e)
stack += e;
else
stack.pop_back();
}
return stack;
}
};