欢迎光临
我们一直在努力

[宝宝也能看懂的活动篇][30-Day LeetCoding Challenge] 第九天 比较含退格的字符串

比较含退格的字符串

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

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

题目描述

给定 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”。

提示:

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

官方难度

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;
}

总结

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

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

相关链接

qrcode_green.jpeg

https://segmentfault.com/a/1190000022319828

赞(0)
未经允许不得转载:ITyet » [宝宝也能看懂的活动篇][30-Day LeetCoding Challenge] 第九天 比较含退格的字符串
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址