LeetCode 844. 比较含退格的字符串

约 6 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 微软
标签
字符串 双指针 栈 模拟

题目描述

✅ 844. 比较含退格的字符串

image-20260929104957028

image-20260929104957254

题意分析

将两个字符串分别输入空文本，其中 # 删除此前仍然保留的最后一个字符；空文本上的退格无效。比较的是全部输入完成后的文本，原字符串长度可以不同，最终结果也可能为空。

解法：双指针从后往前跳过退格

核心思路

[!blue]

正序读取时，一个字母是否保留还取决于后面的退格。反过来从右向左读，就能先遇到会影响它的全部退格，因此不必像栈模拟那样构造最终文本。

两个字符串各维护一个指针和退格计数 skip。遇到 #，表示还要跳过左侧一个普通字符，令 skip 加一；遇到普通字符且 skip > 0，就跳过它并把计数减一；普通字符遇到 skip == 0 时，它不会再被右侧退格删除，就是最终文本从右向左的下一个字符。

分别找到两个下一个有效字符后再比较：字符不同就失败，只有一侧还有有效字符也失败；相同则两边指针都左移，继续比较剩余部分。每个有效字符都按最终顺序配对，全部配对结束就说明两串相等。

字符耗尽后，剩余退格只相当于在空文本上删除，可以忽略。代码用值为 0 的字符表示「已经没有有效字符」；题目只含小写字母和 #，因此这个标记不会与输入字母混淆。

解题步骤

  1. 两个指针分别从字符串末尾开始。
  2. 只要任一原串还有未处理位置，就分别向左跳过退格和被删字符，停在下一个有效字符或字符串之外。
  3. 比较两侧有效字符，耗尽的一侧用 0 表示，不同时返回 false。
  4. 相同时让两个指针各左移一次，继续下一轮；遍历结束后返回 true。

代码实现

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

        while (i >= 0 || j >= 0) {
            // 倒序先累计退格，再跳过对应数量的普通字符，停在下一有效字符。
            while (i >= 0) {
                char c = s.charAt(i);

                if (c == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }

            while (j >= 0) {
                char c = t.charAt(j);

                if (c == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }

            char a = i >= 0 ? s.charAt(i) : 0;
            char b = j >= 0 ? t.charAt(j) : 0;

            if (a != b) {
                return false;
            }

            i--;
            j--;
        }

        return true;
    }
}

func backspaceCompare(s string, t string) bool {
    i, j := len(s)-1, len(t)-1
    skipS, skipT := 0, 0

    for i >= 0 || j >= 0 {
        // 倒序先累计退格，再跳过对应数量的普通字符，停在下一有效字符。
        for i >= 0 {
            if s[i] == '#' {
                skipS++
                i--
            } else if skipS > 0 {
                skipS--
                i--
            } else {
                break
            }
        }
        for j >= 0 {
            if t[j] == '#' {
                skipT++
                j--
            } else if skipT > 0 {
                skipT--
                j--
            } else {
                break
            }
        }

        var a byte = 0
        var b byte = 0
        if i >= 0 {
            a = s[i]
        }
        if j >= 0 {
            b = t[j]
        }
        if a != b {
            return false
        }
        i--
        j--
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n+m)$，每个指针只向左移动。
  • 空间复杂度：$O(1)$，只保存指针与退格计数。

关键点总结

[!green]

  • 先识别井号，再判断普通字符是否需要删除。
  • 两串使用各自的退格计数，独立寻找有效字符。
  • 比较最终字符顺序，不比较原字符串长度。
  • 每个指针只向左移动，满足线性时间、常数额外空间的进阶要求。

易错点总结

[!yellow]

  • 用一个布尔值记录退格：不能表达连续多个删除。
  • 只要一串耗尽就返回 true：另一串可能还剩未配对的有效字符，必须继续处理。
  • 下标已经为负仍读取字符：退格可能把全部内容删除。
  • 将退格理解为删除右侧字符：与实际输入顺序相反。

相似题目

题目 难度 关联与区别
2390. 从字符串中移除星号 中等 退格语义相同，原题返回删除后的文本，本题比较两串结果，还可从右向左跳过被删除字符。
1047. 删除字符串中的所有相邻重复项 简单 同样使用栈消除前缀末尾内容，原题由相邻相同字符触发，本题由退格符触发。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/35507567
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！