力扣题目链接[1]
给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例1:
输入:"abbaca"
输出:"ca"
解释:
例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
「提示:」
1 <= S.length <= 20000
S
仅由小写英文字母组成。思路:
本题可以使用栈的思路来解决。依次将字符串的字符放入栈中,同时判断栈顶元素是否与当前字符相等,如果相等,则弹出栈顶元素;如果不相等则将当前字符放入栈顶。最终剩下的元素所拼接成的字符串就是没有相邻项的结果。这里每次循环都弹出一个字符,用来判断与接下来需要比较的字符是否相等,如果相等则全部丢弃,继续判断下一个字符,如果不相等则按照顺序全部放入栈中。
/**
* @param {string} s
* @return {string}
*/
var removeDuplicates = function(s) {
let stack = []; // 初始化栈
let idx = 0; // 初始化指针变量,用来指向字符串中的字符
while (idx < s.length) { // 循环条件
const top = stack.pop(); // 弹出元素
s[idx] !== top ? stack.push(top, s[idx++]) : idx++; // 处理上述逻辑,并指针右移
}
return stack.join(''); // 返回栈中残留的元素拼接成的字符串
};
其实本题还可以使用双指针的思路进行求解。将字符串分隔为数组,并维护快慢指针。当开始循环时,首先将快指针的元素覆盖到慢指针上。然后判断慢指针的元素和上一个元素是否相同,如果相同,则将慢指针递减,方便下一次循环进行覆盖。如果不相同则慢指针递增。每次循环都需要将快指针不断递增。
也就是说,快指针负责不断往前走获取新的字符,慢指针负责判断相邻元素是否重复,如果重复则丢弃,并在下一次将快指针的元素覆盖到递减过的慢指针元素上,从而继续判断相邻元素是否重复。
最后将数组截取到慢指针所在位置,并拼接为字符串返回即可。
/**
* @param {string} s
* @return {string}
*/
var removeDuplicates = function(s) {
let arr = s.split('');
let fast = 0;
let slow = 0;
while(fast < s.length) {
arr[slow] = arr[fast];
if (slow > 0 && arr[slow] === arr[slow - 1]) slow--;
else slow++;
fast++;
}
return arr.slice(0, slow).join('');
};
本题考查栈的应用,难度系数简单。还需记住栈的特点「后进先出」。
[1]
力扣题目链接: https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/