给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true。# 代表退格字符。
思路
- 栈。时间空间复杂度较高
- 快慢指针。分别处理
学习点
- 在原始
s和t上进行修改，只需要额外的O(1)空间复杂度和O(2*n)时间复杂度。快指针查找，慢指针写入
代码
栈
// 栈
class Solution {
public:
bool backspaceCompare(string s, string t) {
string s_res = "";
string t_res = "";
stack<char> ss;
stack<char> ts;
for (int i = 0; i < s.size(); i++)
{
if (s[i] != '#')
{
ss.push(s[i]);
}
else
{
if (!ss.empty())
ss.pop();
}
}
while (!ss.empty())
{
s_res += ss.top();
ss.pop();
}
// reverse(s_res.begin(), s_res.end());
for (int i = 0; i < t.size(); i++)
{
if (t[i] != '#')
{
ts.push(t[i]);
}
else
{
if (!ts.empty())
ts.pop();
}
}
while (!ts.empty())
{
t_res += ts.top();
ts.pop();
}
// reverse(t_res.begin(), t_res.end());
return (s_res == t_res);
}
};快慢指针
// 快慢指针
class Solution {
public:
bool backspaceCompare(string s, string t) {
// 快慢指针
int s_slow = 0;
for (int fast = 0; fast < s.size(); ++fast)
{
// not '#'
if (s[fast] != '#')
s[s_slow++] = s[fast];
// is '#'
else
{
if (s_slow > 0)
{
s_slow--;
}
}
}
// 新 s 长度为 s_slow
int t_slow = 0;
for (int fast = 0; fast < t.size(); ++fast)
{
// not '#'
if (t[fast] != '#')
t[t_slow++] = t[fast];
// is '#'
else
{
if (t_slow > 0)
{
t_slow--;
}
}
}
// 新 t 长度为 t_slow
// length is not equal
if (s_slow != t_slow)
return false;
// length is equal
else
{
for (int i = 0; i < s_slow; i++)
{
// 存在一个不一样
if (s[i] != t[i])
return false;
}
return true;
}
}
};
