【代码随想录刷题记录】LeetCode844比较含退格的字符

本文主要是介绍【代码随想录刷题记录】LeetCode844比较含退格的字符，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址

1. 思路

1.1 基本思路

拿到这个题，我们要单独写一个函数去将退格后的字符串结果返回出来（生成退格后的真实的字符串），我还是想魔改 $O (n)$ 时间复杂度的删除数组元素的算法：【代码随想录刷题记录】LeetCode27移除元素
那我们就需要思考一下，这个算法中的slow和fast指针的关系，我们都知道，当遇到要删除的元素，slow会停下来，而fast会继续自增，而我们要删除的元素的范围实际上是[slow, fast)，左闭右开，我们看一下之前的代码：

class Solution {
public:// 引用传递，直接改nums，是改其本身，不是拷贝int removeElement(vector<int>& nums, int val) {int slow = 0; //慢指针，用来记录删除该元素后，每个元素对应的新下标slowfor(int fast = 0; fast < nums.size(); fast++){if(val != nums[fast]){// 下一次循环必须先执行赋值操作再进行slow的自增nums[slow] = nums[fast];slow++;}       }return slow;}
};

假设我们要删除的是3，数组nums是[1,1,3,3,2]
fast=0：

由于 $\text{nums[fast]}=\text{nums}[0]=1\ne\text{val}=3$ ，则

fast=1：

由于 $\text{nums[fast]}=\text{nums}[1]=1\ne\text{val}=3$ ，则

fast=2：

由于 $\text{nums[fast]}=\text{nums}[2]=3=\text{val}=3$ ，则什么也不做，进入下一次循环

fast=3：

由于 $\text{nums[fast]}=\text{nums}[3]=3=\text{val}=3$ ，则什么也不做，进入下一次循环
fast=4：

由于 $\text{nums[fast]}=\text{nums}[4]=2\ne\text{val}=3$ ，则

这个时候，循环就停止了，slow是新数组的长度，但是我们仔细看到这个删除的过程，在最后一轮循环的时候，删除的范围是[slow, fast)，即

那我们再一次回看这个删除的区间和现在的这个题目，我们要删除的是#和#之前的字符，那我们的删除的区间就是[slow-1,fast)，那就说明， fast所指元素在遍历的时候如果是#（也就是增加了一个else条件），那就应该让slow自减，但是slow自减只有在slow下标合法也即slow不是0的时候才能自减，我们把上面那个数组换成字符串即[a,b,#,#,c]

如果我们想要单纯删除#，当然还可以保持原有的逻辑，但是我们要删除的区间要扩大，相当于退了两个单位（假设没有nums[slow]=nums[fast]这个过程）

这个才是我们理想的删除情况，它的具体过程应该追溯到fast为2的时候（因为之前的流程和没加else条件的slow–是一样的）：
fast=2：

由于 $\text{nums[fast]}=\text{nums}[2]=\#=\text{val}=\#$ ，则slow–

fast=3：

由于 $\text{nums[fast]}=\text{nums}[3]=\#=\text{val}=\#$ ，则slow–

此时，我们成功找到了删除的区间
fast=4：

由于 $\text{nums[fast]}=\text{nums}[4]=\text{c}\ne\text{val}=\#$ ，则

这个时候,slow对应的是新字符串的长度,新字符串中只有一个字符c
但是单纯地加上这样一个else条件也是不行的，如果字符串是[#, #, c]的话，最开始遇到#退格，slow会向左越界，会变成-1，所以只有在slow没到0的时候（也即大于0的时候）才能slow自减。
我们生成退格后的真实的字符串后，再对比两个字符串就能返回出结果。

1.2 代码实现

从上面的内容得知，代码实现如下，这次没有做验证，直接顺利通过：

class Solution {
public://生成退格后的真实的字符串string genRealString(string s){int n = s.size(); // 字符串长度int slow = 0;string result = ""; // 要返回的字符串for (int fast = 0; fast < n; fast++){//当前遇到不是#就自增，和O(n)时间复杂度删除数组中某个元素的方法类似if (s[fast] != '#'){s[slow] = s[fast];slow++;}//不同于删除数组中某个元素的方法，它需要在遇到#后让slow后退一个位置//因为我们要删除的是#之前的字符else{//如果slow没向左越界就自减，因为假设#在下标为0的位置，则其退格//相当于没退格，但是#需要删除,所以此时slow不需要自减1//其他情况需要自减1（将要删除元素的范围是#和其前面的元素，//删除元素的范围是[slow,fast)，所以slow自减是为了将#之前的元素删除if(slow > 0){slow--;}}}result = s.substr(0, slow); // 截取从0开始，长度为slow的字符串return result;}bool backspaceCompare(string s, string t) {string a = genRealString(s);string b = genRealString(t);return a == b;}
};