51-比较含退格的字符串

自己的做法

算法思想

使用栈，将字符串的每个字符依次入栈，如果遇到#，那么就弹栈。即去掉栈顶元素，结束遍历后。依次弹栈连接成新的字符串，不含退格符。

两个字符串都做如上操作，然后进行比较即可。

需要注意：对空文本进行退格，还是空文本。所以在遇到退格符时，需要判断栈是否为空，不为空，才弹栈。

算法实现

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stack<char> stack;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == '#') {
                if(!stack.empty()) {
                    stack.pop();
                }
            } else {
                stack.push(s[i]);
            }
        }
        s = "";
        while (!stack.empty()) {
            s = s + stack.top();
            stack.pop();
        }
        //再做一遍
        for(int i = 0; i < t.size(); i++) {
            if(t[i] == '#') {
                if(!stack.empty()) {
                    stack.pop();
                }
            } else {
                stack.push(t[i]);
            }
        }
        t = "";
        while (!stack.empty()) {
            t = t + stack.top();
            stack.pop();
        }
        return s == t;

    }
};

性能分析

时间复杂度：$O(m + n)$。m为s的长度，n为t的长度。

空间复杂度：$O(max(m, n))$。较长的字符串的长度。

参考做法

第一种和我的相同。

只说第二种。

算法思想

使用双指针。

在遍历字符串时，当遇到#退格符时，就代表该退格符的前一个字符应被删去，是无效字符。

所以当从头到尾遍历时，要去掉的是它的前一个字符。

所以可以从尾到头遍历，每当遇到一个#时，就知道下次遍历到的字符如果不是#，是正常字符就应该被删去。

所以定义两个变量skip_s和skip_t。代表当前应被删去的字符数量。

即：如果当前遍历的字符为正常字符，且skip不为0，那么该字符就是无效字符，如果为0，就代表当前字符是有效字符。

当遇到#时，就加 1。

所以思路就有了。

定义两个变量i和j初始值，分别为s和t的最后一个字符的索引。

skip_s和skip_t初始为0。

首先找到s的一个有效字符，然后再找t的一个有效字符。比较这两个字符，如果不相同，直接返回false。

当然有一种情况是：其中一个字符串遍历完了，而另一个还没有，这种情况两个字符串肯定不相同，返回false。

如果两个字符串全部遍历完毕，代表这两个字符串相等，返回true。

算法实现

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int skip_s = 0, skip_t = 0;
        int i = s.size() - 1, j = t.size() - 1;
        //当两个字符串全都遍历完成结束循环
        while ( i >= 0 || j >= 0) {
            //找到s的有效字符
            while (i >= 0) {
                if(s[i] == '#') {
                    skip_s++;
                    i--;
                } else if(skip_s > 0) {
                    skip_s--;
                    i--;
                } else {
                    //当s[i]为正常字符，且skip_s 为0时，该字符就是有效字符
                    break;
                }
            }
            //找到t的有效字符
            while (j >= 0) {
                if(t[j] == '#') {
                    skip_t++;
                    j--;
                } else if(skip_t > 0) {
                    skip_t--;
                    j--;
                } else {
                    break;
                }
            }
            //如果两个指针都有效，比较对应的字符
            if(i >= 0 && j >= 0) {
                if(s[i] != t[j]) {
                    return false;
                }
                //有一个指针有效，而另一个无效(即已经遍历完成)，就返回false
            } else if(i >= 0 || j >= 0) {
                    return false;
            }
            i--, j--;
        }
        return true;
    }
};

性能分析

时间复杂度：$O(m +n)$。

空间复杂度：$O(1)$。