【微软】比较含退格的字符串（简单）

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

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

示例 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 = “b”
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。

提示：
1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 ‘#’

方法一：自己的方法，栈 2ms

  1. class Solution {
  2.     public boolean backspaceCompare(String s, String t) {
  3.         Stack<Character> ss = new Stack<>();//LIFO
  4.         Stack<Character> tt = new Stack<>();
  5.         for(char c : s.toCharArray()){
  6.             if(c != '#'){
  7.                 ss.push(c);
  8.             }else{
  9.                 if(!ss.isEmpty()){
  10.                     ss.pop();
  11.                 }
  12.             }
  13.         }
  14.         for(char c : t.toCharArray()){
  15.             if(c != '#'){
  16.                 tt.push(c);
  17.             }else{
  18.                 if(!tt.isEmpty()){
  19.                     tt.pop();
  20.                 }
  21.             }
  22.         }
  23.         while(!ss.isEmpty() && !tt.isEmpty()){
  24.             if(ss.pop() != tt.pop()){
  25.                 return false;
  26.             }
  27.         }
  28.         if(ss.isEmpty() && tt.isEmpty()){
  29.             return true;
  30.         }
  31.         return false;
  32.     }
  33. }

方法二：重构字符串（StringBuilder）1ms

class Solution {
    public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }

    public String build(String str) {
        StringBuffer ret = new StringBuffer();
        int length = str.length();
        for (int i = 0; i < length; ++i) {
            char ch = str.charAt(i);
            if (ch != '#') {
                ret.append(ch);
            } else {
                if (ret.length() > 0) {
                    ret.deleteCharAt(ret.length() - 1);
                }
            }
        }
        return ret.toString();
    }
}

复杂度分析
时间复杂度：O(N+M)，其中 N 和 M 分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。
空间复杂度：O(N+M)，其中 N 和 M 分别为字符串 S 和 T 的长度。主要为还原出的字符串的开销。

方法三：双指针 0ms

一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。

具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：

  • 若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1；
  • 若该字符为普通字符：
    • 若 skip 为 0，则说明当前字符不需要删去；
    • 若 skip 不为 0，则说明当前字符需要删去，我们让 skip 减 1。

这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int sN = s.length(), tN = t.length();
        int i = sN - 1, j = tN - 1;
        int skipS = 0, skipT = 0;
        while (i >= 0 || j >= 0)
        {
            // 先找到 s 中第一个需要比较的字符（即去除 # 影响后的第一个待比较字符）
            while (i >= 0)
            {
                if (s.charAt(i) == '#')
                {
                    skipS ++;
                    i --;
                }
                else if (skipS > 0)
                {
                    skipS --;
                    i --;
                }
                else
                {
                    break;
                }
            }
            // 再找到 t 中第一个需要比较的字符（即去除 # 影响后的第一个待比较字符）
            while (j >= 0)
            {
                if (t.charAt(j) == '#')
                {
                    skipT ++;
                    j --;
                }
                else if (skipT > 0)
                {
                    skipT --;
                    j --;
                }
                else
                {
                    break;
                }
            }
            // 然后开始比较,注意有下面这个 if 条件的原因是：如果 index = 0 位置上为 '#'，则 i, j 会为 -1
            // 而 index = -1 的情况应当处理。
            if (i >= 0 && j >= 0) 
            {
                // 如果待比较字符不同，return false
                if (s.charAt(i) != t.charAt(j))
                    return false;
            }
            // (i >= 0 && j >= 0) 为 false 情况为
            // 1. i < 0 && j >= 0
            // 2. j < 0 && i >= 0
            // 3. i < 0 && j < 0
            // 其中，第 3 种情况为符合题意情况，因为这种情况下 s 和 t 都是 index = 0 的位置为 '#' 而这种情况下
            // 退格空字符即为空字符，也符合题意，应当返回 True。
            // 但是，情况 1 和 2 不符合题意，因为 s 和 t 其中一个是在 index >= 0 处找到了待比较字符，另一个没有找到
            // 这种情况显然不符合题意，应当返回 False，下式便处理这种情况。
            else if (i >= 0 || j >= 0)
                return false;
            i--;
            j--;
        }
        return true;
    }
}

复杂度分析
时间复杂度：O(N+M)，其中 N 和 M 分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。
空间复杂度：O(1)。对于每个字符串，我们只需要定义一个指针和一个计数器即可。