题目:
给定 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”。
思路:
- 首先要获取经过退格字符处理后的最终字符串s和字符串长度slowIndex。
int delBackspace(string & s)利用&改变实参s,得到退格处理后的字符串。
定义两个指针,快指针用来遍历原始字符串,慢指针用来存储处理后的字符串。
遇到字母,两指针都向前一位,遇到#号,快指针向前一位,需要删除字符,所以慢指针后退一位(注意0位置)。 - 得到最终字符串后进行比较。
若最终字符串长度不相等,返回false。
长度相等则逐一比较。
代码:
class Solution {
public:
bool backspaceCompare(string s, string t) {
int s_length = delBackspace(s);
int t_length = delBackspace(t);
if(s_length != t_length) return false;
else
{
for(int i = 0; i < s_length; i++)
{
if(s[i] != t[i]) return false;
}
}
return true;
}
private:
// 获取退格处理后的最终字符串长度slowIndex,并且利用&改变实参s,得到退格处理后的字符串
int delBackspace(string & s)
{
// 慢指针代表退格后的字符串长度
// 快指针遍历字符串
int slowIndex = 0;
for(int fastIndex = 0; fastIndex < s.size(); fastIndex++)
{
// 遇到字母,两指针都向前一位
if(s[fastIndex] != '#')
{
s[slowIndex++] = s[fastIndex];
}
// 遇到#号,快指针向前一位,慢指针后退一位(注意0位置)。
else
{
if(slowIndex > 0)
{
slowIndex--;
}
}
}
return slowIndex;
}
};
总结:
时间复杂度:O(A+B+C),其中 A 和 B 分别为字符串 S 和 T 的长度,C代表处理后的字符串长度。我们需要遍历两字符串和处理后的字符串各一次。
空间复杂度:O(1)。对于每个字符串,我们只需要定义一个指针和长度即可。
- 首先要获取经过退格字符处理后的最终字符串s和字符串长度slowIndex。
- 得到最终字符串后进行比较。
标签:slowIndex,844,int,字符串,长度,退格,指针 From: https://blog.csdn.net/yuan_2001_/article/details/140253851