844.比较含退格的字符串（解法三：双指针）

844. 比较含退格的字符串
给定 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：我们维护两个计数器 skipS 和 skipT，然后开始倒序遍历字符串
步骤2：当我们遇到‘#’时，将对应的计数器 + 1；当我们遇到字符时，会有如下的判断：
如果退格计数器为0，那么该字符无法跳过，此时应该比对当前的字符是否相同
如果退格计数器 >= 0，那么该字符需要跳过，所以需要让遍历指针往前移一位，同时让计数器 – 1
步骤3：如果遍历过程中，发现两个位置上的字符并不相同，或者有其中一个字符串已经遍历完，那么直接返回 false，否则继续往前遍历剩下的字符
最后如果两个字符串都已经遍历完，那么证明它们经过退格的操作后是相等的字符串，返回 true；
时间复杂度是 O(N)
空间复杂度是O(1)

package com.codernav.demo.leetcode.array.removeelement;

/**
 * 844. 比较含退格的字符串
 * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
 * 注意：如果对空文本输入退格字符，文本继续为空。
 * 原文地址：https://www.codernav.com/2905.html
 * 更多算法详解：https://www.codernav.com
 */
public class Q_844_2 {
    public static void main(String[] args) {
        System.out.println(f("ab#c", "ad#c"));
    }

    private static boolean f(String s, String t) {
        int S_Len = s.length(), T_Len = t.length();
        char[] S_arr = s.toCharArray(), T_arr = t.toCharArray();
        int skipS = 0, skipT = 0;
        for (int i = S_Len - 1, j = T_Len - 1; i >= 0 || j >= 0; i--, j--) {
            while (i >= 0) {
                if (S_arr[i] == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    // 遇到字符, 但由于需要回退, 所以还需要前移1位
                    skipS--;
                    i--;
                } else {
                    // 遇到字符, 且不能回退了, 所以需要比对这个字符是否与T对应位置上的字符相等
                    break;
                }
            }
            while (j >= 0) {
                if (T_arr[j] == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S_arr[i] != T_arr[j]) return false;
            } else if (i >= 0 || j >= 0) {
                // 有其中一方已经遍历完整个字符串, 但另外一方没有遍历完整个字符串, 直接返回false
                return false;
            }
        }
        return true;
    }
}