Vue.js

Appearance

On this page

实战：比较含退格的字符串 ​

LeetCode 844. 比较含退格的字符串 | 难度：简单

这道题展示了从后向前的双指针技巧。

题目描述 ​

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

示例 1：

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

示例 2：

输入：s = "a#c", t = "b"
输出：false

思路分析 ​

方法一：栈模拟 ​

遇到普通字符入栈，遇到 # 出栈。最后比较两个栈。

时间 O(n)，空间 O(n)。

方法二：从后向前双指针 ​

空间 O(1) 的做法。

关键洞察：从后向前遍历时，# 会影响它前面的字符，但不会影响后面的。

"ab#c" 从后向前：
c → 保留
# → 记录需要跳过 1 个
b → 跳过
a → 保留
最终：ca → 反过来就是 ac

代码实现 ​

typescript
function backspaceCompare(s: string, t: string): boolean {
  let i = s.length - 1;
  let j = t.length - 1;
  let skipS = 0;  // s 中需要跳过的字符数
  let skipT = 0;  // t 中需要跳过的字符数
  
  while (i >= 0 || j >= 0) {
    // 找到 s 中下一个有效字符
    while (i >= 0) {
      if (s[i] === '#') {
        skipS++;
        i--;
      } else if (skipS > 0) {
        skipS--;
        i--;
      } else {
        break;
      }
    }
    
    // 找到 t 中下一个有效字符
    while (j >= 0) {
      if (t[j] === '#') {
        skipT++;
        j--;
      } else if (skipT > 0) {
        skipT--;
        j--;
      } else {
        break;
      }
    }
    
    // 比较当前字符
    if (i >= 0 && j >= 0) {
      if (s[i] !== t[j]) return false;
    } else if (i >= 0 || j >= 0) {
      // 一个还有字符，另一个没有了
      return false;
    }
    
    i--;
    j--;
  }
  
  return true;
}

执行过程可视化 ​

s = "ab#c", t = "ad#c"

从后向前遍历 s：
  i=3, s[3]='c' → 保留，当前有效字符 c
  i=2, s[2]='#' → skipS=1，跳过标记
  i=1, s[1]='b' → skipS>0，跳过，skipS=0
  i=0, s[0]='a' → 保留，当前有效字符 a
  最终有效字符序列（反向）：c, a → 正向：ac

从后向前遍历 t：
  j=3, t[3]='c' → 保留
  j=2, t[2]='#' → skipT=1
  j=1, t[1]='d' → 跳过，skipT=0
  j=0, t[0]='a' → 保留
  最终有效字符序列：ac

比较：ac === ac ✓

---

更复杂的例子：s = "a##c", t = "#a#c"

s 从后向前：
  i=3: 'c' → 保留
  i=2: '#' → skipS=1
  i=1: '#' → skipS=2
  i=0: 'a' → 跳过（skipS=1），skipS=1
  i<0，结束
  有效字符：c

t 从后向前：
  j=3: 'c' → 保留
  j=2: '#' → skipT=1
  j=1: 'a' → 跳过，skipT=0
  j=0: '#' → skipT=1，但 j<0
  有效字符：c

结果：相等 ✓

代码逻辑详解 ​

为什么需要嵌套 while 循环？ ​

typescript
while (i >= 0) {
  if (s[i] === '#') {
    skipS++;
    i--;
  } else if (skipS > 0) {
    skipS--;
    i--;
  } else {
    break;  // 找到有效字符，停下来比较
  }
}

这个内层循环处理连续的退格和被删除字符：

  1. 遇到 # → 累加需要跳过的数量
  2. 有待跳过的字符 → 消耗一个跳过次数
  3. 既不是 # 也不需要跳过 → 这是有效字符

关键边界情况 ​

typescript
// 情况1：一个字符串先遍历完
if (i >= 0 && j >= 0) {
  // 两边都有字符，比较
  if (s[i] !== t[j]) return false;
} else if (i >= 0 || j >= 0) {
  // 一边还有字符，另一边没有 → 不相等
  return false;
}

// 情况2：两边都遍历完，进入下一轮
// （此时 i < 0 && j < 0，循环会正常结束）

复杂度分析 ​

  • 时间复杂度：O(m + n)

    • 每个字符最多被访问一次
    • 虽然有嵌套循环，但指针只向左移动

  • 空间复杂度：O(1)

    • 只使用了四个变量：i、j、skipS、skipT

栈解法对比 ​

typescript
function backspaceCompareStack(s: string, t: string): boolean {
  return process(s) === process(t);
}

function process(str: string): string {
  const stack: string[] = [];
  
  for (const char of str) {
    if (char === '#') {
      stack.pop();  // 退格，弹出一个字符
    } else {
      stack.push(char);
    }
  }
  
  return stack.join('');
}
解法时间空间优势
栈O(m+n)O(m+n)直观易懂
双指针O(m+n)O(1)空间最优

常见错误 ​

错误1：从前向后遍历 ​

typescript
// ❌ 错误：从前向后无法知道后面有多少 #
for (let i = 0; i < s.length; i++) {
  // 当遇到字符时，不知道后面会不会有 # 删除它
}

错误2：忘记处理连续退格 ​

typescript
// ❌ 错误：只处理一次退格
if (s[i] === '#') {
  skipS++;
  i--;
}
// 如果有 "a##"，需要连续处理两个 #

错误3：边界条件判断遗漏 ​

typescript
// ❌ 错误：只检查 i >= 0 || j >= 0
while (i >= 0 || j >= 0) {
  // 正确的条件，但内部比较时要考虑
  // 其中一个可能已经 < 0 的情况
}

相关题目 ​

  • 1047. 删除字符串中的所有相邻重复项：类似的字符消除思想
  • 20. 有效的括号：栈的另一个经典应用
  • 394. 字符串解码：更复杂的嵌套结构处理

要点 ​

从后向前遍历的双指针技巧，适用于需要处理"影响前面元素"的场景。核心思想是：

  1. 反向思考：# 影响它前面的字符，所以从后向前处理更自然
  2. 累计影响：用计数器记录需要跳过的字符数
  3. 同步比较：两个字符串各自找到有效字符后再比较

在 GitHub 上编辑此页