leetcode844:比较含退格的字符串

题干

在这里插入图片描述

题目分析

两个字符串要进行比较，#代表着回车，也就是删除之前的字符。
若按照遍历的惯例，选择从前到后遍历，但这样没法判断，因为#之前被删除的部分是不需要相同的。
因此考虑到#的含义，我们应该选择从后往前遍历。

从后往前遍历，若当前下标所指向的字符不是#，需要判断这个数是否是被删除的数，如果不是被删除的数，才需要比较是否相等。

这就引出一个问题————如何判断这个数是否被删除了？以及如何让两个字符串能够比对？

若直接按照下标从后向前遍历，但两个删除后的实际字符串，同一个字符的下标在两个原本的字符串中的下标可能是不相同的。

因此，我们要解决这些问题，我们要实现以下几点：

首先要通过设定变量，记录#的数量。这一步的目的是跳过#前的字符，让下标指引到真正要比对的字符位置
当前位置不是#的时候，我们要判断#的数量，如果不为0，则要跳过此字符，sum要减一
满足时间复杂度O（n），空间复杂度O（1），不可以循环嵌套
判断两个字符串比对时机的条件，当前字符sum为0且不为#的时候进行比对。为了方便比对，两个字符串的遍历要在同一个循环里面，这样才能确保每一轮比对都是对应的。

由此，我们开始进行代码的编写。

代码撰写与空间复杂度优化

常规的比较简单的方法，是使用StringBuffer或者StringBuilder，因为String是不可变的，而StringBuilder是可变的，因此使用StringBuilder可以直接删除不合适的字符，并返回最终字符串，将两个最终字符串进行比对。

代码如下：

class Solution {public boolean backspaceCompare(String s, String t) {String s1 = fun(s);String s2 = fun(t);return s1.equals(s2);}private String fun(String s){int c = 0;StringBuilder ss = new StringBuilder();for (int i = s.length() - 1; i >= 0; i--){if (s.charAt(i) != '#'){if (c == 0){ss.append(s.charAt(i));} else {c--;}} else {c++;}}return ss.toString();}
}

但这个代码并不符合题目的要求，因为它使用了额外的空间存储两个字符串（创建了StringBuilder）
因此它的空间复杂度为O（m+n），不符合O（1）的要求。

为改进这个问题，按照之前分析的思路，我们使用字符串遍历，跳过#删除的字符的方法，一一进行比对

代码如下：
从后往前遍历的时候，我们考虑3中情况

第一种：当前字符为#，记录#数量的sum++，指针前移
第二种：当前字符不为#，但sum数不为0，证明这个位置的字符是要被跳过的，因此sum–，指针前移
第三种：当前字符不为#，sum数为0，证明这个是删除后保留的字符，也就是要被进行比对的字符，此时通过break关键字退出循环，此刻slow指针所指向的下标便是本轮循环中要进行比对的下标。

class Solution {public boolean backspaceCompare(String s, String t) {int slow1 = s.length() - 1; int slow2 = t.length() - 1; while (slow1 >= 0 || slow2 >= 0) {int backspaceCount1 = 0;while (slow1 >= 0) {if (s.charAt(slow1) == '#') {backspaceCount1++; slow1--;} else if (backspaceCount1 > 0) {backspaceCount1--; slow1--;} else {break; }}int backspaceCount2 = 0;while (slow2 >= 0) {if (t.charAt(slow2) == '#') {backspaceCount2++; slow2--;} else if (backspaceCount2 > 0) {backspaceCount2--; slow2--;} else {break; }}if (slow1 >= 0 && slow2 >= 0) {if (s.charAt(slow1) != t.charAt(slow2)) {return false; }} else if (slow1 >= 0 || slow2 >= 0) {return false; }slow1--;slow2--;}return true;}
}

（这里可以用其他名字，比如t、j代替slow1，slow2，我这样写是因为写快慢指针的时候写习惯了所以用slow代指用来赋值的指针。）

思路易错点

被删除的字符要一个一个跳过

else if (backspaceCount1 > 0) {backspaceCount1--; slow1--;}

我们分析这段代码，会发现遇到不是#，且sum不为0的字符时，我们跳过当前字符，sum–。
在初次分析的时候，我选择了slow=slow-sum；sum=0；来进行跳过多个字符。

但这样是错误的，以为批量跳过的时候，有可能跳过#，这样会导致程序逻辑上的错误。
因此我们要一一比对，精准记录每一个#字符

比对时，条件判断要精准

            if (slow1 >= 0 && slow2 >= 0) {if (s.charAt(slow1) != t.charAt(slow2)) {return false; }} else if (slow1 >= 0 || slow2 >= 0) {return false; }