栈-844.比较含退格的字符串-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 17:27:34

3500

代码可运行

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

运行总次数：0

代码可运行

一、题目解析

1、#代表退格字符，可以理解为删除

2、s和t中只有小写字符以及字符'#'

二、算法原理

解法：栈模拟

通过string简单模拟栈，得到的结果不需要额外转换

对于即将加入的元素是‘#’，我们对字符串pop_back()，尾删处理

细节：题目上给出了空串遇到‘#’的处理，结果仍然为空，所以我们在判断删除或加入字符串之前需要特殊处理一下

三、代码示例

class Solution {
public:
    bool backspaceCompare(string s, string t)
    {
        string ret1,ret2;
        for(int i = 0;i<s.size();i++)
        {
            if(s[i] == '#'&&ret1.size()==0) continue;//特判对空串退格
            if(s.size()>0&&s[i] == '#')
                ret1.pop_back();
            else ret1 += s[i];
        }
        for(int j = 0;j<t.size();j++)
        {
            if(t[j] == '#'&&ret2.size()==0) continue;
            if(t.size()>0&&t[j] == '#')
                ret2.pop_back();
            else ret2 += t[j];
        }
        return ret1 == ret2;
    }
};