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);}
};