比较含退格的字符串

Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列特别篇 - 30-Day LeetCoding Challenge。这是一个 leetcode 官方的小活动。可以在官网看到，从 4 月 1 号开始，每天官方会选出一道题，在 24 小时内完成即可获得一点小奖励。

这里是 4 月 9 号的题，也是题目列表中的第 844 题 -- 『比较含退格的字符串』

题目描述

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

示例 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”。

提示：

• 1 <= S.length <= 200
• 1 <= T.length <= 200
• S 和 T 只含有小写字母以及字符 '#'。

官方难度

EASY

解决思路

喵喵喵，直白而又干脆的题目。关键的核心点就是，'#' 代表的退格操作，行为是向左删除上一个字符，也就意味着左边的字符都是不稳定的。抓住这个点就可以让我们后续的实现简单很多。这里提供两种思路：

• 记录结果的过程中模拟这种退格行为。
• 从稳定的字符开始处理。

模拟退格

首先是第一种思路 -- 模拟退格。如果我们自己控制逻辑来处理的话，多少会有点麻烦。所以这里直接借助了栈这个数据结构的特性，即后进先出，来方便的模拟退格的逻辑。具体流程如下：

1. 遍历字符串。
2. 如果遇到非 '#' 字符，则把字符压栈。
3. 如果遇到 '#' 字符，则进行弹栈操作。
4. 遍历完成后即是处理完的结果。

基于以上流程，我们只需要分别获取两个输入字符串的最终处理结果，然后进行比较即可。具体代码如下：

const decode = s => {
  const stack = [];
  for (const c of s) {
    c === '#' ? stack.pop() : stack.push(c);
  }
  return stack.join('');
};
const backspaceCompare = (s1, s2) => decode(s1) === decode(s2);

从稳定字符开始处理

上面的方案存在额外的空间复杂度，那么我们是否可以优化掉这一部分呢？我们尝试一下这种从稳定字符开始处理的思路。

这种思路的核心就是，我们每一步都去获取一个稳定的字符，然后进行比较即可。什么是稳定的字符？即不会因为还没处理的退格行为再发生变化的字符。那么相信小伙伴们很容易能想到，我们可以从尾部开始处理，便不用对于历史内容进行储存了，也就可以优化掉额外的空间复杂度了。

具体流程如下：

1. 从尾部开始遍历两个字符串。
2. 如果遇到非 '#' 字符，则暂停下来，以备比较。
3. 如果遇到 '#' 字符，则记录数量，并继续向前移动指针，直到需要退格的数量回归到 0。
4. 将两个字符串中当前的稳定字符进行比较，不同则返回 false。
5. 全部比较完成后，返回 true。

const backspaceCompare = (s1, s2) => {
  let p1 = s1.length - 1;
  let p2 = s2.length - 1;
  while (p1 >= 0 || p2 >= 0) {
    for (let bs = 0; s1[p1] === '#' || bs > 0; --p1) {
      s1[p1] === '#' ? ++bs : --bs;
    }
    for (let bs = 0; s2[p2] === '#' || bs > 0; --p2) {
      s2[p2] === '#' ? ++bs : --bs;
    }
    if (s1[p1--] !== s2[p2--]) return false;
  }
  return true;
}

总结

第一种思路是一种比较典型的栈结构的应用场景，即我们需要根据后面的数据来重新修改前面的内容。不知道看过之前小猪周赛题解的小伙伴们是否还记得，我们曾经也遇到过很类似的逻辑。希望能帮助小伙伴们识破这种套路！

如果觉得不错的话，记得『三连』哦。小猪爱你们哟~

相关链接

• 活动题目列表
• leetcode 题解 repo
• 我的 segmentfault 专栏
• 我的知乎专栏