【力扣精选算法100道】——带你了解(数组模拟栈)算法

目录

💻比较含退格的字符串

🎈了解题意 

🎈分析题意

🚩栈

🚩数组模拟栈

🎈实现代码

844. 比较含退格的字符串 - 力扣（LeetCode）

💻比较含退格的字符串

🎈了解题意 

如果遇到#那么就删除前面的字符，

• 比如 s=ab#c   遇到#的时候我们就删除b,然后往后依次遍历后最终的结果是ac，t=ad#c,遇到#删除d ，然后往后依次遍历后最终的结果是 ac，字符串s和字符串t最终的字符串是ac相同那么就返回 true。
• 比如 s="a#c" 最终的结果是 c，t="b" 最终的结果是 b,字符串s和字符串t是不同的，所以返回false。

🎈分析题意

🚩栈

字符串 s中遇到 # 就删除栈顶元素，然后遍历下一个元素，如果不等于#，就入栈。

字符串 t 中遇到#就删除栈顶元素d，然后遍历下一个元素，如果不等于# 就继续入栈。

 字符串 s中遇到 # 就删除栈顶元素，然后遍历下一个元素，如果不等于#，就入栈c。

字符串 t 中遇到#就删除栈顶元素d，然后遍历下一个元素，如果不等于# 就继续入栈c。

最终字符串s="c" t="ac" 此时s不等于t，返回false。

🚩数组模拟栈

字符串中删除最后一个字符用到 pop.back()。

🎈实现代码

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string ret1;
        for(auto ch:s)
        {
            if(ret1.size() && ch=='#') ret1.pop_back();
            else if(ch!='#')ret1+=ch;
        }

        string ret2;
        for(auto ch:t)
        {
            if(ret2.size() && ch=='#') ret2.pop_back();
            else if(ch!='#') ret2+=ch;
        }
        return ret1==ret2;
    }
};

别看到别人发光就觉得自己黯淡。