1047.删除字符串中的所有相邻重复项
文章目录
- 1047.删除字符串中的所有相邻重复项
- 一、题目
- 二、题解
- 方法一:栈
- 算法思路
- 具体实现
- 算法分析
- 方法二:双指针
- 算法思路
- 具体实现
- 算法分析
- 三、一些拓展
- 栈的应用场景和原理
一、题目
给出由小写字母组成的字符串 S
,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例:
输入:"abbaca"
输出:"ca"
解释:
例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
提示:
1 <= S.length <= 20000
S
仅由小写英文字母组成。
二、题解
方法一:栈
算法思路
我们可以遍历字符串 s
的每个字符,然后使用一个栈来存储非重复的字符。遍历过程中,我们将当前字符与栈顶的字符进行比较,如果相同,则将栈顶的字符弹出;如果不同,则将当前字符入栈。最后,我们将栈中的字符按照逆序组合成结果字符串即可。
具体实现
- 初始化一个空栈
st
和空字符串result
用于存储结果。 - 遍历字符串 s的每个字符 c:
- 如果栈不为空且
c
等于栈顶的字符,说明c
与前一个字符重复,因此将栈顶的字符弹出; - 否则,将
c
入栈。
- 如果栈不为空且
- 遍历完所有字符后,栈中剩余的字符就是去除相邻重复字符后的结果,我们将它们从栈顶开始依次取出并拼接到
result
字符串的末尾。 - 最后,将
result
字符串进行逆序操作,得到最终的结果。 - 返回逆序后的
result
。
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
for (char c : s) {
if (!st.empty() && c == st.top()) {
st.pop();
} else {
st.push(c);
}
}
string result;
while (!st.empty()) {
result += st.top();
st.pop();
}
reverse(result.begin(), result.end());
return result;
}
};
算法分析
- 时间复杂度分析:遍历字符串的时间复杂度为 O(n),其中 n 是字符串的长度。栈的操作时间复杂度为 O(1),逆序操作的时间复杂度为 O(n)。因此,总体时间复杂度为 O(n)。
- 空间复杂度分析:空间复杂度主要取决于栈和结果字符串。栈的最大空间为字符串中不重复字符的数量,最坏情况下为 O(n)。结果字符串的空间为 O(n)。因此,总体空间复杂度为 O(n)。
方法二:双指针
算法思路
双指针法是一种常用的技巧,通过使用两个指针在数组或字符串上移动,实现对元素的遍历和操作。对于本题,我们可以使用双指针来删除相邻重复项。具体思路如下:
- 初始化两个指针
i
和j
,其中i
指向结果字符串的末尾位置,而j
用于遍历原始字符串。 - 遍历原始字符串 s:
- 如果
i
大于 0 且当前字符s[j]
等于结果字符串中最后一个字符s[i-1]
,说明遇到了相邻重复项,需要将其删除。因此,将指针i
左移一位,相当于删除了重复项。 - 否则,将不重复的字符
s[j]
移动到指针i
的位置,并将指针i
右移一位,继续处理下一个字符。
- 如果
- 最后,返回结果字符串
s
的前i
个字符,即为去重后的字符串。
具体实现
class Solution {
public:
string removeDuplicates(string s) {
int n = s.length();
int i = 0; // 指向结果字符串的末尾位置
for (int j = 0; j < n; j++) {
if (i > 0 && s[j] == s[i - 1]) {
i--; // 删除重复项,指针左移
} else {
s[i++] = s[j]; // 将不重复的字符移动到指针位置
}
}
return s.substr(0, i); // 返回去重后的字符串
}
};
算法分析
- 时间复杂度分析:该算法只需要一次遍历原始字符串,因此时间复杂度为 O(n),其中 n 是字符串的长度。
- 空间复杂度分析:由于算法只使用了常数级的额外空间,因此空间复杂度为 O(1)。
三、一些拓展
栈的应用场景和原理
栈是一种常见的数据结构,它遵循先进后出(LIFO)的顺序。除了在删除相邻重复项问题中的应用外,栈还在计算机科学的许多领域中发挥着重要作用。例如,在编程语言的函数调用中,栈被用于存储局部变量和函数调用信息;在网页浏览器的返回按钮中,栈用于存储浏览历史记录。栈的实现可以使用数组或链表,常见的操作包括入栈(push)、出栈(pop)、获取栈顶元素(top)等。