(字符串) 844. 比较含退格的字符串——【Leetcode每日一题】

这篇具有很好参考价值的文章主要介绍了(字符串) 844. 比较含退格的字符串——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

❓844. 比较含退格的字符串

难度:简单

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

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

示例 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 = “b”
输出:false
解释:s 会变成 “c”,但 t 仍然是 “b”。

提示

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

进阶

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

💡思路:

法一:栈

  • 使用栈将给定的字符串中的退格符 # 和 应当被删除的字符都去除;
  • 然后比较栈中两字符串是否相等即可。

法二:优化方法(从后向前双指针)

我们定义两个指针,分别指向两字符串的末尾( i 初始为 s 末尾,j 初始为 t 末尾),同时从后向前遍历 st

再定义 s_skipt_skip 表示当前待删除的字符的数量。

每次我们遍历到一个字符:

  • 该字符为退格符 # ,则我们需要多删除一个普通字符,我们让 skip1
  • 若该字符为普通字符,让 skip1;。

每次我们让两指针逆序地遍历两字符串,直到两字符串能够各自确定一个字符,然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等,或遍历完字符串为止。

动画如下:
(字符串) 844. 比较含退格的字符串——【Leetcode每日一题】

🍁代码:(Java、C++)

法一:栈
Java

class Solution {
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> stk1 = new Stack<>();
        Stack<Character> stk2 = new Stack<>();
        for(char c : s.toCharArray()){
            if(c != '#') stk1.push(c);
            else if(!stk1.empty()) stk1.pop();
        }
        for(char c : t.toCharArray()){
            if(c != '#') stk2.push(c);
            else if(!stk2.empty()) stk2.pop();
        }
        if(stk1.size() != stk2.size()) return false;
        while(!stk1.empty()){
            if(stk1.peek() != stk2.peek())return false;
            stk1.pop();
            stk2.pop();
        }
        return true;
    }
}

C++

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stack<char> stk1, stk2;
        for(char c : s){
            if(c != '#') stk1.push(c);
            else if(!stk1.empty()) stk1.pop();
        }
        for(char c : t){
            if(c != '#') stk2.push(c);
            else if(!stk2.empty()) stk2.pop();
        }
        if(stk1.size() != stk2.size()) return false;
        while(!stk1.empty()){
            if(stk1.top() != stk2.top())return false;
            stk1.pop();
            stk2.pop();
        }
        return true;
    }
};

法二:优化方法(从后向前双指针)
Java

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        int s_skip = 0, t_skip = 0;
        while(true){
            while(i >= 0 && (s.charAt(i) == '#' || s_skip > 0)){// 从后向前,消除s的#
                if(s.charAt(i) == '#') s_skip++;
                else s_skip--;
                i--;
            }
            while(j >= 0 && (t.charAt(j) == '#' || t_skip > 0)){// 从后向前,消除t的#
                if(t.charAt(j) == '#') t_skip++;
                else t_skip--;
                j--;
            }
            // 后半部分#消除完了,接下来比较s[i] != t[j]
            if (i < 0 || j < 0) break; // s 或者t 遍历到头了
            if (s.charAt(i) != t.charAt(j)) return false;
            i--;j--;
        }
        return i == j;
    }
}

C++

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i = s.size() - 1, j = t.size() - 1;
        int s_skip = 0, t_skip = 0;
        while(1){
            while(i >= 0 && (s[i] == '#' || s_skip > 0)){// 从后向前,消除s的#
                if(s[i] == '#') s_skip++;
                else s_skip--;
                i--;
            }
            while(j >= 0 && (t[j] == '#' || t_skip > 0)){// 从后向前,消除t的#
                if(t[j] == '#') t_skip++;
                else t_skip--;
                j--;
            }
            // 后半部分#消除完了,接下来比较s[i] != t[j]
            if (i < 0 || j < 0) break; // s 或者t 遍历到头了
            if (s[i] != t[j]) return false;
            i--;j--;
        }
        return i == j;
    }
};
🚀 运行结果:

(字符串) 844. 比较含退格的字符串——【Leetcode每日一题】

🕔 复杂度分析:
  • 时间复杂度 O ( n + m ) O(n+m) O(n+m),其中 nm 分别为字符串 st 的长度。我们需要遍历两字符串各一次。
  • 空间复杂度 O ( 1 ) O(1) O(1),对于每个字符串,我们只需要定义一个指针和一个计数器即可。法一为 O ( n + m ) O(n+m) O(n+m)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-514730.html

注: 如有不足,欢迎指正!

到了这里,关于(字符串) 844. 比较含退格的字符串——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C语言】PTA——字符串比较

    编写一个函数实现两个字符串的比较,即自己写一个strcmp函数,函数原型为“int strcmp(char* p1,char* p2);”设p1指向字符串s1,p2指向字符串s2,要求当s1==s2时,函数返回值为0;若s1≠s2,则返回二者中第一个不相同字符的ASCII码差值(如\\\"BOY\\\"与\\\"BAD\\\"的第二个字母不同,\\\'O\\\'与\\\'A\\\'之差为

    2024年02月04日
    浏览(45)
  • Python中的比较两个字符串

    📚 个人网站:ipengtao.com 在Python编程中,字符串比较是一项常见且关键的操作,涵盖了诸多方法和技巧。比较两个字符串是否相等、大小写是否一致,或者在一个字符串中寻找特定的子字符串,都是日常开发中经常遇到的需求。除此之外,使用正则表达式进行模式匹配、比较

    2024年01月19日
    浏览(56)
  • Python实现字符串相似度比较

    Python实现字符串相似度比较 在日常的开发中,我们可能需要对不同的字符串进行比较,以判断它们之间的相似程度。例如,在搜索引擎、拼写检查和数据清洗等任务中,字符串相似度比较是一项非常重要的技术。本文将介绍如何使用Python实现字符串相似度比较。 概述 字符串

    2024年02月06日
    浏览(47)
  • java中比较两字符串是否相等

    字符串比较的三种方式:==,equals,Objects.equals  打印结果 a==b为false 因为两个字符串的索引值不同。 打印结果为  a.equals(b)为true 因为两个字符串的值相同。 所以在java中进行字符串比较时,经常使用equals比较两字符是否相同。一个固定的字符串和字符串数组(或list集合)进行

    2023年04月08日
    浏览(43)
  • Python(八十三)字符串的比较操作

    ❤️ 专栏简介:本专栏记录了我个人从零开始学习Python编程的过程。在这个专栏中,我将分享我在学习Python的过程中的学习笔记、学习路线以及各个知识点。 ☀️ 专栏适用人群 :本专栏适用于希望学习Python编程的初学者和有一定编程基础的人。无论你是学生、职场人士还是

    2024年02月13日
    浏览(54)
  • 【c语言】字符串比较 | API仿真

    创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡𖥦)!! 主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步! 给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ c语言系列专栏:c语言之路重点知识整合 字符串知识点

    2024年02月03日
    浏览(47)
  • C++之string字符串比较方法

    📣📣📣📣📣📣📣📣 ✏️作者主页:枫霜剑客 📋 系列专栏:C++实战宝典 🌲 上一篇: C++之string字符串不同类型间转换 📣📣📣📣📣📣📣📣 🎍逐梦编程,让中华屹立世界之巅。 🎍简单的事情重复做,重复的事情用心做,用心的事情坚持做; 字符串可以和类型相同的字

    2024年02月03日
    浏览(70)
  • Java字符串比较的方法(3种)

    equals()方法将两个字符串每个字符是否相同进行逐一比较,若相同返回true反之返回false,对于字符的大小写也在检查范围内,equals()方法格式如下:str1.equals(str2); equalsIgnoreCase()方法与equals()方法完全相同,唯一不同是equalsIgnoreCase()方法比较时不区分大小写,equalsIgnoreCase()方法格

    2024年02月15日
    浏览(76)
  • C语言修行之函数篇(二)strcasecmp,strncasecmp —— 比较字符串字符

    strcasecmp()函数对字符串s1和s2执行逐字节比较,忽略字符的大小写。如果发现s1分别小于、匹配或大于s2,则返回一个小于、等于或大于0的整数。 函数输入值: s1 / s2 :对比字符串 n:对比个数 函数返回值: strcasecmp()函数在忽略大小写后 如果发现si分别小于、匹配或大于s2,则

    2024年02月07日
    浏览(50)
  • 数据结构(C语言):两个字符串比较大小

    在写这篇文章之前,作者想先和大家分享一个小故事。如果你不想看这个小故事的话,可以直接跳到第二点哦。 为了锻炼自己的编码能力,平时作业和实验题的代码我都是不看书、不看老师的PPT,按照自己的思路一行一行敲出来的。同时也不太理解那些照着书敲代码的同学。

    2024年02月03日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包