本文写于 2020年04月09日,距今已超过 1 年,距 2020年04月09日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

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 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论