leetcode-844-比较含退格的字符串(用vector取代stack)

题目描述:

给定 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. 1 <= S.length <= 200
  2. 1 <= T.length <= 200
  3. S 和 T 只含有小写字母以及字符 '#'

要完成的函数:

bool backspaceCompare(string S, string T) 

说明:

1. 这道题给定两个字符串S和T,字符串中只含有小写字母和#字符,#字符表示退格键,删除掉前一个字符。要求判断两个字符串经过了退格操作后,是否相同。

比如S=“a#b”,T=“c#b”,经过退格操作后,都只剩下b字符,是相同的字符串。再比如S="#ab#",T=“ab#”,经过退格操作后,只剩下a字符,是相同的字符串。

2. 这道题笔者最开始想着能不能不操作字符串,直接通过计算和判断给实现了。后来发现不太可行,就算是人类来做这道题,也是先做退格操作,得到新的两个字符串,接着比较是否一样。所以还是得操作字符串,删去字符。

笔者最开始想用stack来做,碰到#字符就pop(),十分方便,但stack不好的地方在于,你没办法直接知道stack中的所有字符,还得逐个top()和pop()。

如果使用vector来做,同样可以碰到#字符就pop_back(),正常字符就push_back(),而且vector还可以直接读取,快速地比较两个vector是否相同。

最终采用了vector来做,代码如下:

    bool backspaceCompare(string S, string T) 
    {
        vector<char>v1,v2;
        for(char element:S)//处理S中的所有字符,结果存储在v1中
        {
            if(element!='#')
                v1.push_back(element);
            else
            {
                if(!v1.empty())
                    v1.pop_back();
            }
        }
        for(char element:T)//处理T中的所有字符,结果存储在v2中
        {
            if(element!='#')
                v2.push_back(element);
            else
            {
                if(!v2.empty())
                    v2.pop_back();
            }
        }
        if(v1!=v2)//判断得到的v1和v2是否相同
            return false;
        return true;
    }

vector基本上可以取代stack啦!

上述代码实测4ms,beats 93.75% of cpp submission。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

go语言中的interface使用实例

go语言中的interface是一组未实现的方法的集合,如果某个对象实现了接口中的所有方法,那么此对象就实现了此接口。与其它面向对象语言不同的是,go中无需显示...

2254
来自专栏linjinhe的专栏

C++字符串处理小结

常用的C++的字符串类型主要是std::string。它是模板std::basic_string的一个实例化。另外还有三个实例化std::wstring、std...

7328
来自专栏JAVA技术站

shell学习一变量的定义 原

用符号$加上变量名如 $name 或${name},{}括号是为了确定变理边界,推荐使用

661
来自专栏技术碎碎念

python3 入门 (一) 基础语法

1.编码问题 默认情况下,Python 3源码文件以 UTF-8 编码,所有字符串都是 unicode 字符串。 也可以为源码文件指定不同的编码,在文件头部加上...

3057
来自专栏老司机的技术博客

golang学习笔记4:基本类型和运算符

布尔型的值只可以是常量 true 或者 false。一个简单的例子: var b bool = true 。两个类型相同的值可以使用相等 == 或者不等 != ...

2973
来自专栏Python小屋

小议Python列表和元组中的元素地址连续性

众所周知,在Python中字典和集合依赖元素哈希表来存储,并不存在传统意义上的所谓元素“顺序”,当然,如果需要一个有序的字典可以使用collections模块提...

36310
来自专栏Spring相关

带返回值的函数,闭包,沙箱,递归详解

那了解了函数 this 指向的不同场景之后,我们知道有些情况下我们为了使用某种特定环境的 this 引用, 这时候时候我们就需要采用一些特殊手段来处理了,例如...

572
来自专栏码洞

《快学 Go 语言》第 7 课 —— 冰糖葫芦串

字符串通常有两种设计,一种是「字符」串,一种是「字节」串。「字符」串中的每个字都是定长的,而「字节」串中每个字是不定长的。Go 语言里的字符串是「字节」串,英文...

1025
来自专栏北京马哥教育

Python3急速入门 (一) 基础语法

豌豆贴心提醒,这是马哥Linux运维Python3急速入门系列第1篇文章 1.编码问题 默认情况下,Python 3源码文件以 UTF-8 编码,所有字符串都...

3268
来自专栏python3

python3--基础数据类型

切片就是通过索引(索引:索引:步长)截取字符串的一段,形成新的字符串(原则就是顾头不顾尾)

872

扫码关注云+社区

领取腾讯云代金券