比较含退格的字符串

题目链接：https://leetcode-cn.com/problems/backspace-string-compare
题目描述：
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。

示例 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 = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”。

示例 4：
输入：S = "a#c", T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。

提示：
1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小写字母以及字符 '#'。

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

题解：
方法1：模拟栈(O(n))

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        string s;
        string t;
        for(int i = 0; i < S.size(); i++)
        {
            if(S[i] != '#')
                s += S[i];
            else if(!s.empty())
                s.pop_back();
        }
        for(int j = 0; j < T.size(); j++)
        {
            if(T[j] != '#')
                t += T[j];
            else if(!t.empty())
                t.pop_back();
        }
        cout << s << endl;
        cout << t << endl;
        if(s == t)
            return true;
        else
            return false;
    }
};

方法二：双指针（O(1)）

class Solution {
public:
    bool backspaceCompare(string S, string T) {
       int s = 0;   //记录当前有多少个'#'
       int t = 0;
       int i = S.size() - 1;        //从后往前遍历
       int j = T.size() - 1;
       while(1)
       {
            while(i >= 0)       //遍历S字符串
            {
                if(S[i] == '#')
                {
                    s++;
                }else
                {
                    if(s >0)
                    {
                        s--;
                    }else
                    {
                        break;
                    }
                }
                i--;
            }
            
            while(j >= 0)           //遍历T字符串
            {
                if(T[j] == '#')
                {
                    t++;
                }else
                {
                    if(t > 0)
                    {
                        t--;
                    }else
                    {
                        break;
                    }
                }
                j--;
            }
            if(i < 0 || j < 0)      //某一个字符串先遍历完
                break;
            if(S[i] != T[j])        //回退消除完后，比较当前字符
                return false;
            i--;                    //字符相等继续遍历
            j--;
            
        }
        if(i == -1 && j == -1)      //两个字符均遍历完
            return true;
        return false;           
      
    }
};