LeetCode 844. 比较含退格的字符串 (C++实现)
1. 题目描述
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = “ab#c”, t = “ad#c”
输出：true
解释：s 和 t 都会变成 “ac”。
示例 2：
输入：s = “ab##”, t = “c#d#”
输出：true
解释：s 和 t 都会变成 “”。
示例 2：
输入：s = “a#c”, t = “b”
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。
2. 解题思路
分别处理s和t，以s举例，首先定义慢指针slow和快指针fast，遍历字符串元素，如果快指针指向的当前元素不等于#，则将快指针指向位置的值赋给慢指针指向的位置，慢指针向后移动一位，否则继续移动快指针，不赋值，如果快指针指向的当前元素等于#，这时候判断slow指针是否在字符串的起始位置，不是的话减1。循环结束后比较处理之后的s和t是否相同。
3. 代码实现
class Solution {
public:
string change(string str)
{
int slow = 0;
for (int fast = 0; fast < str.size(); fast++)
{
if (str[fast] != '#')
{
str[slow] = str[fast];
slow++;
}
else if (slow > 0)
{
slow--;
}
}
return str.substr(0,slow);
}
bool backspaceCompare(string s, string t) {
return change(s) == change(t);
}
};