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
- s 和 t 只含有小写字母以及字符 ‘#’
进阶：
你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
erase函数
// 定义一个解决方案类
class Solution {
public:
// 定义一个公共成员函数来比较两个字符串 s 和 t
bool backspaceCompare(string s, string t) {
// 调用 my_erase 对字符串 s 进行处理
my_erase(s);
// 调用 my_erase 对字符串 t 进行处理
my_erase(t);
// 如果处理后的 s 和 t 相等，返回 true
if(s == t) return true;
// 否则返回 false
return false;
}
private:
// 定义一个私有成员函数 my_erase，以引用方式接收字符串 str 并在原地修改
void my_erase(string& str)
{
// 遍历字符串 str
for(int i = 0; i < str.size(); ++i)
{
// 如果当前字符是退格符 #
if(str[i] == '#')
// 如果不位于字符串的开始位置
if(i != 0)
{
// 删除前一个字符和当前的 # 字符
str.erase(i - 1, 2);
// 将索引 i 向后移动两个位置，以重新检查新的当前位置的字符
i -= 2;
}
else
{
// 如果位于字符串的开始位置，只删除 # 字符
str.erase(i, 1);
// 将索引 i 向后移动一个位置
i -= 1;
}
}
}
};
双指针
class Solution {
public:
bool backspaceCompare(string s, string t) {
// 初始化两个指针分别指向字符串 s 和 t 的末尾
int i=s.size()-1,j=t.size()-1;
// 初始化两个变量用来记录需要退格的字符数
int nums=0, numt=0;
// 遍历两个字符串直到所有字符都被比较过
while(i>=0||j>=0)
{
// 在 s 中找到下一个应该比较的字符
while(i>=0)
{
//如果遇到退格符，增加 s 中需要跳过的字符数，并且指针向前移动
if(s[i]=='#') nums++, i--;
// 如果有字符需要跳过，减少需要跳过的字符数，并且指针向前移动
else if(nums>0) nums--, i--;
// 找到了应该比较的字符，跳出循环
else break;
}
// 在 t 中找到下一个应该比较的字符
while(j>=0)
{
if(t[j]=='#') numt++,j--;
else if(numt>0) numt--,j--;
else break;
}
// 比较 s 和 t 中的字符,如果字符不同，返回 false
if(i>=0&&j>=0&&s[i]!=t[j])
return false;
// 如果一个字符串结束而另一个没有结束，也返回 false
if ((i >= 0) != (j >= 0))//相当于if(i>=0&&j<0||j>=0&&i<0)
return false;
// 移动指针准备比较下一对字符
i--,j--;
}
// 所有字符都匹配，返回 true
return true;
}
};
