题目描述

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

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

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

样例

输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。

输入：S = "ab##", T = "c#d#"
输出：true
解释：S 和 T 都会变成 “”。

输入：S = "a##c", T = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”。

算法1

(栈模拟) $O(n)$

我们可以单独的用栈模拟，我们从前向右遍历，遇到#就弹出前面的字符.大概做法就是这样。具体看代码。

C++ 代码

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        string s;//栈模拟
        string t;//栈模拟   
        int n = S.size(),m = T.size();
        for (int i = 0;i < n;i ++){
            if (S[i] == '#'){//当遇到#,弹出前面的字符
                if (s.size()){
                    s.pop_back();
                }
            }
            else s += S[i];
        }
        for (int i = 0;i < m;i ++){
            if (T[i] == '#'){
                if (t.size()){
                    t.pop_back();
                }
            }
            else t += T[i];
        }
        if (s == t) return true;
        return false;
    }
};

算法2

(双指针) $O(n)$

我们从前向后遍历S和T数组，模拟遇到#就“删除”，当退出所有循环的时候，i == -1 j == -1时时true，其他情况就是 false。

C++ 代码

class Solution {
public:
    bool backspaceCompare(string S, string T) {
       int i = S.size() - 1;
       int j = T.size() - 1;
       int snum = 0, tnum = 0;
       while(1){
           while(i >= 0){
               if (S[i] == '#') snum ++;//记录个数
               else {
                   if (snum > 0) snum --;// 向前移动
                   else break;
               }
               i --;
           }
            while(j >= 0){
               if (T[j] == '#') tnum ++;
               else {
                   if (tnum > 0) tnum --;
                   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;
    }
};