LeetCode 844 比较含退格的字符串

力扣 844 比较含退格的字符串 | LeetCode 844 Backspace String Compare | 算尽天下系列第 11 期 | 栈/双指针

题目描述

给定 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”。

算法与数据结构

栈

双指针

题解

这道题可以用一个栈来模拟退格的操作，遍历字符串，遇到新字符就入栈，遇到退格键就出栈，最后比较两个栈内的元素是否相等，非常简单。

但是如果要求只使用 O(1) 的空间呢？这道题的难度一下子就可以上升好几个数量级。

下面分享一种使用双指针来完成这道题的方法，只需要使用 O(1) 的辅助空间。

从前往后遍历字符串的时候，遇到一个字符，我们是没有办法知道这个字符最终会不会属于这个字符串，因为我们没有办法知道后面会有多少个退格，但是从后往前遍历字符串的时候，我们有办法知道一个字符是不是属于这个字符串。

那么，我们可以从后往前遍历字符串，记 i 和 j 分别表示当前两个字符串的比较位置，初始均为 strlen() - 1。

若当前位置的字符不相等（S[i] != T[j]），则直接 return false 而无需继续往前比较，若当前位置的字符相等，那么继续往前比较。

现在还需要处理一个退格的问题。

若遇到 S[i] == '#'，那么就要数一数有多少个退格键，每遇到一个退格键，skipS++，表示接下来要跳过多少个字符。那么，当 skipS > 0 时，我们依旧需要持续地令 i--; skipS--;，不断的跳过那些被删除了的字符。

需要注意的有两点：一，在这个过程中，S[i] 依旧有可能等于 '#'，此时我们非但不应该进行 skipS--，反而应该进行 skipS++。二，在退格操作完成后，紧接着的那个字符也有可能是 '#'，因此退格操作应持续进行到 S[i] != '#' 为止。

对于 T 也是一样的。

只要 i 和 j 中有任何一个还大于 0，就应该持续该过程，直到两者都小于 0，此时输出 true。

由于字符串长度可能不等，退格键的按下次数可能会超过已经输入的字符数，例如 a###########b，所以应该时刻注意上面所有的条件判断中要加上 i >= 0 和 j >= 0 的判断。

这样，在上面过程中的任何一处出现 (i >= 0 && j < 0) 或者 (i < 0 && j >= 0) 都将是不合法的。

完整代码

bool backspaceCompare(char * S, char * T){
    int i = strlen(S) - 1;
    int j = strlen(T) - 1;
    int skipS = 0;
    int skipT = 0;
    while (i >= 0 || j >= 0) {
        while (i >= 0 && S[i] == '#') {
            while (i >= 0 && S[i] == '#') {
                skipS++;
                i--;
            }
            while (i >= 0 && skipS > 0) {
                if (S[i] == '#') {
                    skipS++;
                } else {
                    skipS--;
                }
                i--;
            }
        }
        while (j >= 0 && T[j] == '#') {
            while (j >= 0 && T[j] == '#') {
                skipT++;
                j--;
            }
            while (j >= 0 && skipT > 0) {
                if (T[j] == '#') {
                    skipT++;
                } else {
                    skipT--;
                }
                j--;
            }
        }
        if (i >=0 && j >= 0) {
            if (S[i] != T[j]) {
                return false;
            } else {
                i--;
                j--;
            }
        } else {
            return i < 0 && j < 0;
        }
    }
    return true;
}

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) { // While there may be chars in build(S) or build (T)
            while (i >= 0) { // Find position of next possible char in build(S)
                if (S.charAt(i) == '#') {skipS++; i--;}
                else if (skipS > 0) {skipS--; i--;}
                else break;
            }
            while (j >= 0) { // Find position of next possible char in build(T)
                if (T.charAt(j) == '#') {skipT++; j--;}
                else if (skipT > 0) {skipT--; j--;}
                else break;
            }
            // If two actual characters are different
            if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j))
                return false;
            // If expecting to compare char vs nothing
            if ((i >= 0) != (j >= 0))
                return false;
            i--; j--;
        }
        return true;
    }
}