【栈】删除字符串中的所有相邻重复项 && 比较含退格的字符串

利刃大大

发布于 2025-02-20 07:44:30

4600

代码可运行

文章被收录于专栏：csdn文章搬运csdn文章搬运

运行总次数：0

代码可运行

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

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

解题思路：栈思想

这道题其实就像消消乐游戏，如果我们是对原字符串进行删除操作的话，那么其实时间复杂度是比较高的，所以我们考虑用一个字符串来搭载这些不相邻重复项，最后返回即可！

而遍历过程中，我们可以使用栈的思想，判断当前栈顶是否有元素，有的话判断栈顶元素是否和当前元素重复，因为栈顶元素就是字符串相对的上一个位置，所以我们就直接将栈顶元素 pop 掉即可！而如果不相等的话，则直接让当前元素入栈即可！

但因为这道题是字符串操作，我们还去用一个 stack 容器的话，最后还得对字符串进行逆序，就很麻烦，所以我们可以 直接拿 string 当作一个栈进行操作，操作过程和对 stack 操作是一样的，并且可以一步到位！

class Solution {
public:
    string removeDuplicates(string s) {
        string ret;
        for(int i = 0; i < s.size(); ++i)
        {
            if(ret.size() != 0 && ret.back() == s[i]) // 只有栈元素不为空且栈顶元素等于s[i]才进行出栈（变成了字符串操作）
                ret.pop_back();
            else
                ret += s[i];
        }
        return ret;
    }
};

844. 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意： 如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 '#'

进阶：

你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

解题思路：栈思想

这道题也是一样，因为我们需要记录下当前元素前面的字符情况，所以可以使用栈的思想来解决问题，但是我们 并不需要真的使用一个栈，而是可以用题目要求的 string 来模拟栈的操作，即先进后出，这样子就能达到题目的进阶的空间复杂度的要求！

解题过程还是比较简单的：

先将两个字符串通过栈的思想，生成各自去掉退格后的新字符串
最后比较两个新字符串是否相同即可

需要注意的是，在 pop 元素的时候，需要判断栈即字符串是否为空，是的话是不能进行 pop 操作的！

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        // 先将两个字符串通过栈变成去掉退格的字符串
        string tmps, tmpt;
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] != '#')
                tmps.push_back(s[i]);
            else if(tmps.size() != 0) // 注意需要判断栈（字符串）元素不为空的情况
                tmps.pop_back();
        }
        for(int i = 0; i < t.size(); ++i)
        {
            if(t[i] != '#')
                tmpt.push_back(t[i]);
            else if(tmpt.size() != 0) // 注意需要判断栈（字符串）元素不为空的情况
                tmpt.pop_back();
        }

        // 比较两者是否相同
        return tmps == tmpt;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-19，如有侵权请联系 cloudcommunity@tencent.com 删除

容器