leetcode-844-比较含退格的字符串（用vector取代stack）
leetcode-844-比较含退格的字符串（用vector取代stack）
chenjx85
发布于 2018-08-01 15:40:52
发布于 2018-08-01 15:40:52
题目描述：
给定 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 <= 2001 <= T.length <= 200S和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。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-07-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录