专栏首页码农UP2ULeetCode | 844. 比较含退格的字符串

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

题目描述

题目直接从 LeetCode 上截图过来,题目如下:

这道题目是要进行向前的消除,当满足条件时,除了消除当前的字符,也会消除当前字符之前的字符,此时可以使用栈结构来进行操作。时间复杂度和空间复杂度,都为O(N)。

本题我使用 Java 语言来完成,LeetCode 给出的 Java 定义如下:

class Solution {
    public boolean backspaceCompare(String s, String t) {

    }
}

题目分析

题目中给出两个字符串,分别时 S 和 T。字符串中使用 “#” 表示删除键,会删除它前面的字符,比如 S = “a##c” 这个字符串,字符串的结果为 “c”,T = “#a#c”,字符串的结果也为“c”,这样 S 和 T 是相等的。

画图来模拟整个字符串的过程,如下图。

首先,字符串 S 的值为 “ab#c”,我们依次来遍历每个字符。

第一步,当前字符是 a,字符 a 入栈,当前栈中是 a;

第二步,当前字符是 b,字符 b 入栈,当前栈中是 ab;

第三步,当前字符是 #,字符 # 表示删除键,那么就将前一步的字符删除,即将第二步的字符 b 出栈,当前栈中是 a;

最后一步,当前字符是 c,字符 c 入栈,当前栈中是 ac。

这样,字符串 S 的值为 "ac"。

因为,题目要求是比较 S 和 T 是否相等,那么就把 T 也按照此方法进行处理,处理后出栈进行比较即可。

代码实现

看一下我写的 Java 代码,代码如下。

class Solution {
    public boolean backspaceCompare(String s, String t) {
        if (s.length() == 0 && t.length() == 0) {
            return true;
        }

        final Stack<String> ss = new Stack();
        final Stack<String> st = new Stack();

        final int slen = s.length();
        final int tlen = t.length();

        final char del = '#';

        for (int i = 0; i < slen; i ++) {
            if (s.charAt(i) == del && ss.empty()) {
                continue;
            }
            if (s.charAt(i) == del) {
                ss.pop();
                continue;
            }
            ss.push(s.substring(i, i + 1));
        }

        for (int i = 0; i < tlen; i ++) {
            if (t.charAt(i) == del && st.empty()) {
                continue;
            }
            if (t.charAt(i) == del) {
                st.pop();
                continue;
            }
            st.push(t.substring(i, i + 1));
        }

        while (!ss.empty() && !st.empty()) {
            if (!ss.peek().equals(st.peek())) {
                return false;
            }
            ss.pop();
            st.pop();
        }

        if (ss.empty() && st.empty()) {
            return true;
        }

        return false;
    }
}

代码中前两个 for 循环用来完成字符串的处理,后面的 while 循环用来完成两个字符串的比较,代码非常的简单。

提交结果

在写完 backspaceCompare 方法体后,点击右下角的 “执行代码”,然后观察 “输出” 和 “预期结果” 是否一致,一致的话就点击 “提交” 按钮。点击 “提交” 按钮后,系统会使用更多的测试用例来测试我们写的函数体,如果所有的测试用例都通过了,那么就会给出 “通过” 的字样,如果没有通过,会给出失败的那一组测试用例,我们继续修改代码。

本文分享自微信公众号 - 码农UP2U(gh_3c91b47a82e0),作者:码农UP2U

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    Michael阿明
  • LeetCode 844 比较含退格的字符串

    力扣 844 比较含退格的字符串 | LeetCode 844 Backspace String Compare | 算尽天下系列第 11 期 | 栈/双指针

    凝神长老
  • leetcode-844-比较含退格的字符串(用vector取代stack)

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

    chenjx85
  • leetcode栈之比较含退格的字符串

    这里借助栈,遍历string的char,遇到#时在栈不为空的时候pop一下,非#时则push数据到栈中;之后对比两个栈的元素来判断是否相等。

    code4it
  • leetcode栈之比较含退格的字符串

    这里借助栈,遍历string的char,遇到#时在栈不为空的时候pop一下,非#时则push数据到栈中;之后对比两个栈的元素来判断是否相等。

    code4it
  • 【leetcode刷题】T24-比较含退格的字符串

    Given two strings S and T, return if they are equal when both are typed into emp...

    木又AI帮
  • 数据结构——栈

    大家先想象一下这个场景:当我们去打羽毛球时,通常会带一桶羽毛球,不管我们是要拿出还是放入一个羽毛球,都要从最上面拿,如果想拿到下方的羽毛球,必须先把上面的拿出来...

    三猫
  • 脚撕LeetCode(844)Easy

    题目地址:https://leetcode-cn.com/problems/range-sum-query-mutable/

    用户6203048
  • 【一天一大 lee】比较含退格的字符串 (难度:简单) - Day20201019

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

    前端小书童
  • 算法_比较字符串&字符串密钥格式

    比较两个字符串 A 和 B,确定 A 中是否包含 B 中所有的字符。字符串 A 和 B 中的字符都是 大写字母

    OBKoro1
  • 移除个元素就这么难?

    题目地址:https://leetcode-cn.com/problems/remove-element/

    代码随想录
  • 图解 | 不就是栈吗

    栈(stack)是一种先进后出,后出先进的数据结构。之所以这样,是因为栈是操作受限的线性表,允许元素进出的一端称为栈顶(top),不允许元素进出的一端称为栈底(...

    五分钟学算法
  • [每日一题]字符串的比较

    思来想去,相信大家一些基本的语法都差不多了,今天就给大家看一题 题目描述 输入三个字符串,按由小到大的顺序输出 输入 3行字符串 输出 按照从小到大输出成3行...

    编程范 源代码公司
  • Leetcode题解——717/844

    由于10, 11两个编码都是以1开头的,这意味着只要是以1开头的后面一个数必定是根这个1一起的字符编码。利用这一点:

    出其东门
  • Tcl的字符串操作:比较字符串

    在Tcl中,可利用stringcompare命令对字符串进行比较。该命令需要接收两个字符串参数。如果第一个字符串在字典中先于第二个字符串,返回-1;如果第一个字...

    Lauren的FPGA
  • python 下字符串格式时间比较

    python 下有多个有关时间的模块,分别是time、datetime、calendar,今天重点讨论下time写法。

    黯然销魂掌
  • LeetCode-算法-双指针-第18天

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

    布衣者
  • JavaScript字符串间的比较

    字符串在JavaScript中几乎无处不在,在你处理用户的输入数据的时候,在读取或设置DOM对象的属性时,在操作cookie时,当然还有更 多…。@雪斌在Jav...

    晚晴幽草轩轩主
  • #Python3中字符串的比较

    20.字符串的比较 从第一个字符开始比较谁的ASCII值谁就大 如果前面相同 则比较后一位直到比较出谁大 如果都相同 则相等

    py3study

扫码关注云+社区

领取腾讯云代金券