LeetCode 844 - 比较含退格的字符串（Backspace String Compare）

算法刷题>LeetCode>面试经典150
4.9k words

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

问题描述

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例

示例 1：

1
2
3
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

1
2
3
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

1
2
3
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

约束条件

  • 1 <= s.length, t.length <= 200
  • s 和 t 只含有小写字母以及字符 '#'

进阶要求

你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

解题思路

这道题的核心是模拟退格操作，然后比较两个字符串是否相等。有两种主要思路：

方法一：栈模拟（直观解法）

核心思想：使用栈来模拟文本编辑器的行为

  • 遇到普通字符：入栈
  • 遇到 #：出栈（如果栈不为空）
  • 最后比较两个栈的内容

方法二：双指针逆向遍历（最优解法）

核心思想：从后往前遍历，跳过被退格的字符

  • 维护两个指针分别从两个字符串的末尾开始
  • 遇到 # 时，跳过下一个有效字符
  • 比较当前有效字符是否相等

实现细节

栈模拟法

  1. 构建有效字符串：

    • 遍历字符串，遇到普通字符就加入栈
    • 遇到 # 就从栈中弹出字符（如果栈不为空）

  2. 比较结果：

    • 将两个栈转换为字符串进行比较

双指针法

  1. 逆向遍历：

    • 从字符串末尾开始向前遍历
    • 遇到 # 时，记录需要跳过的字符数量

  2. 跳过被退格的字符：

    • 当 skip 计数大于 0 时，跳过当前字符
    • 遇到 # 时，skip 计数加 1

  3. 比较有效字符：

    • 找到两个字符串的下一个有效字符进行比较

代码实现

方法一：栈模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean backspaceCompare(String s, String t) {
    return buildString(s).equals(buildString(t));
}

private String buildString(String str) {
    Stack<Character> stack = new Stack<>();
    
    for (char c : str.toCharArray()) {
        if (c != '#') {
            stack.push(c);
        } else if (!stack.isEmpty()) {
            stack.pop();
        }
    }
    
    return String.valueOf(stack);
}

方法二：双指针（最优解）

核心思想

双指针方法的核心思想是从后往前遍历，这样可以避免处理退格字符的复杂性。当我们从后往前遍历时，遇到 # 就记录需要跳过的字符数量，然后跳过相应数量的字符，直到找到下一个有效字符进行比较。

算法步骤

  1. 初始化指针：两个指针分别指向两个字符串的末尾
  2. 逆向遍历：从右往左遍历两个字符串
  3. 处理退格：遇到 # 时记录跳过计数，遇到普通字符时根据跳过计数决定是否跳过
  4. 比较字符：找到两个字符串的下一个有效字符进行比较
  5. 边界处理：处理字符串长度不同的情况

详细实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1;  // s 的指针，从末尾开始
    int j = t.length() - 1;  // t 的指针，从末尾开始
    
    // 只要还有字符需要处理就继续循环
    while (i >= 0 || j >= 0) {
        // 找到 s 的下一个有效字符
        int skipS = 0;
        while (i >= 0) {
            if (s.charAt(i) == '#') {
                skipS++;  // 遇到退格，增加跳过计数
                i--;
            } else if (skipS > 0) {
                skipS--;  // 跳过当前字符
                i--;
            } else {
                break;    // 找到有效字符，跳出循环
            }
        }
        
        // 找到 t 的下一个有效字符
        int skipT = 0;
        while (j >= 0) {
            if (t.charAt(j) == '#') {
                skipT++;  // 遇到退格，增加跳过计数
                j--;
            } else if (skipT > 0) {
                skipT--;  // 跳过当前字符
                j--;
            } else {
                break;    // 找到有效字符，跳出循环
            }
        }
        
        // 比较两个有效字符
        if (i >= 0 && j >= 0) {
            // 两个字符串都还有字符，比较是否相等
            if (s.charAt(i) != t.charAt(j)) {
                return false;
            }
        } else if (i >= 0 || j >= 0) {
            // 一个字符串已经遍历完，另一个还有字符，不相等
            return false;
        }
        
        // 移动指针到下一个位置
        i--;
        j--;
    }
    
    return true;
}

代码逐步执行样例

以 s = "ab#c", t = "ad#c" 为例，详细展示双指针的执行过程：

初始状态：

1
2
3
s = "ab#c"  (索引: 0,1,2,3)
t = "ad#c"  (索引: 0,1,2,3)
i = 3, j = 3

第1轮循环：

1
2
3
4
5
6
i = 3, j = 3
s[3] = 'c', t[3] = 'c'
都不是 '#'，skipS = 0, skipT = 0
找到有效字符：s[3] = 'c', t[3] = 'c'
比较：'c' == 'c' ✓
i = 2, j = 2

第2轮循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
i = 2, j = 2
s[2] = '#', t[2] = '#'
都是退格字符：
- s: skipS = 1, i = 1
- t: skipT = 1, j = 1
继续处理：
- s: s[1] = 'b', skipS = 1 > 0，跳过，skipS = 0, i = 0
- t: t[1] = 'd', skipT = 1 > 0，跳过，skipT = 0, j = 0
继续处理：
- s: s[0] = 'a', skipS = 0，找到有效字符 'a'
- t: t[0] = 'a', skipT = 0，找到有效字符 'a'
比较：'a' == 'a' ✓
i = -1, j = -1

第3轮循环：

1
2
3
i = -1, j = -1
i < 0 && j < 0，循环结束
返回 true

执行过程可视化：

1
2
3
4
5
步骤1: 比较 'c' 和 'c' → 相等
步骤2: 遇到 '#' 和 '#' → 跳过下一个字符
步骤3: 跳过 'b' 和 'd' → 继续向前
步骤4: 比较 'a' 和 'a' → 相等
结果: 两个字符串都变成 "ac" → 返回 true

边界情况处理

情况1：全为退格字符

1
2
3
4
5
s = "###", t = "##"
执行过程：
- s: 跳过所有字符，最终 i = -1
- t: 跳过所有字符，最终 j = -1
- 两个字符串都为空，返回 true

情况2：一个字符串更长

1
2
3
s = "a#c", t = "b"
执行过程：
- 第1轮：比较 'c' 和 'b' → 不相等，返回 false

情况3：连续退格

1
2
3
4
5
s = "ab##c", t = "a#c"
执行过程：
- s: 遇到 "##"，跳过 "b" 和 "a"，有效字符为 'c'
- t: 遇到 "#"，跳过 'a'，有效字符为 'c'
- 比较 'c' 和 'c' → 相等，返回 true

执行过程示例

以 s = "ab#c", t = "ad#c" 为例：

栈模拟法执行过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
s = "ab#c":
- 'a' → stack: ['a']
- 'b' → stack: ['a', 'b']  
- '#' → stack: ['a'] (弹出 'b')
- 'c' → stack: ['a', 'c']
结果: "ac"

t = "ad#c":
- 'a' → stack: ['a']
- 'd' → stack: ['a', 'd']
- '#' → stack: ['a'] (弹出 'd')
- 'c' → stack: ['a', 'c']
结果: "ac"

比较: "ac" == "ac" → true

双指针法执行过程：

1
2
3
4
5
6
初始: i=3, j=3
s[3]='c', t[3]='c' → 相等，i=2, j=2
s[2]='#', t[2]='#' → 都是退格，跳过下一个字符
s[1]='b', t[1]='d' → 被跳过
s[0]='a', t[0]='a' → 相等
结果: true

方法比较

方面 栈模拟法 双指针法
时间复杂度 O(n + m) O(n + m)
空间复杂度 O(n + m) O(1)
优点 思路直观，易于理解 空间效率高，符合进阶要求
缺点 需要额外空间 实现相对复杂
推荐度 ★★★☆☆ ★★★★★

复杂度分析

栈模拟法

  • 时间复杂度：$O(n + m)$，其中 n 和 m 分别是两个字符串的长度
  • 空间复杂度：$O(n + m)$，需要两个栈来存储字符

双指针法

  • 时间复杂度：$O(n + m)$，每个字符最多被访问一次
  • 空间复杂度：$O(1)$，只使用了常数额外空间

关键收获

  1. 双指针技巧：当需要从后往前处理字符串时，双指针是很好的选择
  2. 退格模拟：遇到退格字符时，需要跳过下一个有效字符
  3. 边界处理：注意处理字符串长度不同的情况
  4. 空间优化：在满足时间复杂度要求的前提下，尽量优化空间复杂度

常见陷阱

  1. 空字符串处理：当字符串全为 # 时，结果应该是空字符串
  2. 指针越界：确保在访问字符前检查索引是否有效
  3. 跳过逻辑：正确处理连续的 # 字符

相关问题