算法|题解

LeetCode 844 比较含退格的字符串

凝神长老 · 4月9日 · 2020年 · · · · · 255次已读

LeetCode 844 比较含退格的字符串

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

题目描述

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

样例

示例 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) 的辅助空间。

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

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

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

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

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

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

对于 T 也是一样的。

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

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

0 0 投票
Article Rating
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论