01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第197题（顺位题号是844）。给定两个字符串S和T，如果两个字符串都输入到空文本编辑器中并且相等，则返回true。 ＃表示退格符。例如：
输入：S =“ab＃c”，T =“ad＃c”
输出：true
说明：S和T都变为“ac”。
输入：S =“ab ##”，T =“c＃d＃”
输出：true
说明：S和T都变为“”。
输入：S =“a ## c”，T =“＃a＃c”
输出：true
说明：S和T都变为“c”。
输入：S =“a＃c”，T =“b”
输出：false
说明：S变为“c”而T变为“b”。
注意：
1 <= S.length <= 200
1 <= T.length <= 200
S和T仅包含小写字母和“＃”字符。
跟进：能在O（N）时间和O（1）空间解决它吗？
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
题目的意思是遇到一个#号就往前去掉一个字母，最后比较两个字符串是否相等。因为是往前去掉字母，所以可以从后往前处理。
解题思路就是从后往前遍历字符串中的字符，统计遇到的#号个数，直到遇上字母为止，然后跳过相同数量（前面统计的#号的数量）的字母，然后累加字符，变成一个新的字符串，将另外一个字符串也按照同样的方式处理。
处理字符串S和T的思路、过程都一样，因此将其抽离出来单独作为一个方法使用。
public boolean backspaceCompare(StringS,StringT) {returnrebuild(S).equals(rebuild(T));}publicStringrebuild(Stringstr){intn =str.length(), count =0;StringnewStr ="";for(inti=n-1; i >=0; i--) {charch =str.charAt(i);if(ch =='#') { count++; }else{if(count >0) { count--; }else{ newStr += ch; } } }returnnewStr;}
03 第二种解法
利用栈。
和上面第一种的解法类似，也是转换成新的字符串，只不过是使用栈来实现，借助其先进后出的特性。
依旧是遍历字符串中的字符，如果当前字符不是#号，就入栈；如果遇到#号，就需要回退一个字符，只需要将栈顶的元素出栈即可，但是需要先判断栈中是否包含元素。
publicbooleanbackspaceCompare2(String S, String T){returnrebuildUseStack(S).equals(rebuildUseStack(T));}publicStringrebuildUseStack(String str){ Stackstack=newStack();for(charch : str.toCharArray()) {if(ch !='#') {stack.push(ch); }elseif(!stack.isEmpty()) {stack.pop(); } }returnString.valueOf(stack);}
04 第三种解法
利用双指针。
上面两种解法都将原字符串替换成了新的字符串去比较是否相等，我们也可以不使用这种方法，借助双指针，通过依次比较对应字符来实现。
定义两个指针，从后往前遍历，找到需要比较的字符的索引位置（#号和对应要去掉的字母排除），比较对应的字符是否相等，如果字符不相等或者其中有一个指针先为0了，可以直接返回false。
publicbooleanbackspaceCompare3(String S, String T){inti = S.length()-1, j = T.length()-1;while(i >=0|| j >=0) { i = helper(S, i); j = helper(T, j);// 判断当前i和j对应的字符是否相等if(i >=0&& j >=0&& S.charAt(i) != T.charAt(j)) {returnfalse; }// 如果i或者j小于0时，判断两者是否同时小于0if(i <0|| j <0) {returni == j; }// 继续向前i--; j--; }returntrue;}/** * 找到下一个需要进行字符比较的索引位置 *@paramstr *@paramindex *@return*/publicinthelper(String str,intindex){intcount =0;while(index >=0) {if(str.charAt(index) =='#') {// 对遇上的#号记数count++; index--; }elseif(count >0) {// 过滤掉#号前面对应个数的字母count--; index--; }else{break; } }returnindex;}
进群：697699179可以获取Java各类入门学习资料！
这是我的微信公众号【编程study】各位大佬有空可以关注下，每天更新Java学习方法，感谢！
学习中遇到问题有不明白的地方，推荐加小编Java学习群：697699179内有视频教程 ，直播课程 ，等学习资料，期待你的加入
