[数据结构与算法]844. 比较含退格的字符串

题目描述: 给定 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) 的空间复杂度解决该问题吗？
来源： 力扣（LeetCode）
链接： https://leetcode-cn.com/problems/backspace-string-compare
解决方案:
思路一: 构造栈, 对于本题最直接的方法就是使用数据结构中的栈结构,构造一个栈, 当遇到退格字符 “#”, 就将退格字符"#“和它的下一个字符出栈。但是这样它的时间复杂度为O(N+M), 分别表示字符串S和T的长度, 空间复杂度也为O(N+M), 主要是申请栈空间所付出的内存开销。
思路二: 双指针法, 该方法可以弥补栈方法带来的时间和空间上多余的开销。由于退格字符”#"只对它的左边字符产生影响, 而不会给它的右边字符带来变化, 因此可以通过逆序遍历方式, 比较两个字符串中的字符是否匹配。

1. 准备两个指针 i 和 j, 分别指向 字符串S，T 的末位字符，再准备两个变量 skipS 和 skipS，分别存放 S，T 字符串中的 # 数量。
2. 从后往前遍历字符串，可能会遇到以下三种情况：
   2.1 若当前字符是 #，则 skipS 自增 1；
   2.2 若当前字符不是 #，且 skipS 不为 0，则 skipS 自减 1；
   2.3 若当前字符不是 #，且 skipS为 0，则代表当前字符不会被消除，可以用来和字符串 T 中的当前字符作比较。

若对比过程出现 S, T 当前字符不匹配，则遍历结束，返回 false，若 S，T 都遍历结束，且都能一一匹配，则返回 true.

	public static boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        // skipS 记录字符串S中退格字符的个数，skipT 记录字符串T中退格字符的个数
        int skipS = 0, skipT = 0;
        // 设置两个指针 i 和 j,从后往前遍历比较 S和 T中的字符
        while (i >= 0 || j >= 0) {
        	// i >=0 表示字符串S遍历尚未结束
            while (i >= 0) {
            	// 如果字符串S中的第i+1个字符为退格字符#
                if (S.charAt(i) == '#') {
                	// 字符串S中的退格字符个数加1
                    skipS++;
                    // 字符串S中的指针向前移一个位置
                    i--;
                } else if (skipS > 0) {
                	// 字符串S中的指针向前移一个位置
                    skipS--;
                    // 字符串S中的指针向前移一个位置
                    i--;
                } else {
                    break;
                }
            }
            // j>=0 表示字符串T遍历尚未结束
            while (j >= 0) {
            	// 如果字符串T中的第j+1个字符为退格字符#
                if (T.charAt(j) == '#') {
                	// 字符串T中的退格字符个数加1
                    skipT++;
                    // 字符串T中的指针向前移一个位置
                    j--;
                } else if (skipT > 0) {
                	// 字符串T中的退格字符个数减1
                    skipT--;
                    // 字符串T中的指针向前移一个位置
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
            	// 字符串S中的第i+1个字符与字符串T中的第j+1个字符不匹配
                if (S.charAt(i) != T.charAt(j)) {
                	// 判定为 false
                    return false;
                }
            } else {
            	// 字符串S或字符串T中只有一个遍历结束
                if (i >= 0 || j >= 0) {
                	// 判定为 false
                    return false;
                }
            }
            // 字符串S中的指针向前移一个位置
            i--;
            // 字符串T中的指针向前移一个位置
            j--;
        }
        return true;
    }

反思: 一开始是想到使用双指针法,从后往前遍历, 但是无奈格局太小, 一直盯着一个字符串看, 想着求出一个字符串最终的结果, 然后再调用同样的方法, 求出另一个字符串的最终结果, 最后对比两个结果, 看是否匹配。最后做下来, 根本没法通过所有的测试用例, 看了别人的题解才明白, 不得不佩服人家以及双指针思想的精妙之处, 继续努力吧!