题目：
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。
示例 2：
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。
示例 3：
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。
提示：
1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 '#'
进阶：
你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/backspace-string-compare
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
方法一：使用栈的思路
- 当 当前字符不为 ‘#’时，将其弹入字符栈中；
- 当当前字符为‘#’ 且字符栈不为空时，弹出字符栈的最后一个字符；
- 最后将两个字符栈中的字符进行比较即可。
可以通过，但是复杂度不满足进阶题意
- 时间复杂度:O(n + m)
- 空间复杂度:O(n + m)
1 class Solution { 2 public boolean backspaceCompare(String s, String t) { 3 return getString(s).equals(getString(t)); 4 5 } 6 public String getString(String s){ 7 StringBuilder sb = new StringBuilder(); 8 for (char c : s.toCharArray()){ 9 if (c != '#'){ 10 sb.append(c); 11 }else if (sb.length() > 0){ 12 sb.deleteCharAt(sb.length() - 1); 13 } 14 } 15 return sb.toString(); 16 } 17 }
方法二：双指针
两个指针i ，j 分别指向字符串s和t 的末尾，countT和countS来统计s 和t 中的 #的数量，从后往前遍历字符串处理过程如下：
- 若当前字符为 # ，则Count值加1；
- 若当前字符不为#且count值不为0，就该处理退格，count值就会减1，字符位置也会减1；
- 以上两种情况的否定即当前字符不为#且count值为0，代表当前字符不会背回退，则用来和另一个字符串中的当前位置做比较；
若对比过程出现S和T 当前字符不匹配，则遍历结束，返回 false，若S，T 都遍历结束，且都能一一匹配，则返回true。
复杂度：
- 时间复杂度:O(n + m)
- 空间复杂度:O(1)
1 class Solution { 2 public boolean backspaceCompare(String s, String t) { 3 int i = s.length() - 1, j = t.length() - 1; 4 //统计字符串中#数量 5 int countS = 0, countT = 0; 6 while (i >= 0 || j >= 0){ 7 //处理s 8 while (i >= 0){ 9 if (s.charAt(i) == '#'){ 10 countS++; 11 i--; 12 }else if (countS > 0){ 13 //这时候就该抵消字符了 14 countS--; 15 i--; 16 }else{ 17 break; 18 } 19 } 20 //处理t 21 while (j >= 0){ 22 if (t.charAt(j) == '#'){ 23 countT++; 24 j--; 25 }else if (countT > 0){ 26 //这时候就该抵消字符了 27 countT--; 28 j--; 29 }else{ 30 break; 31 } 32 } 33 //两个小循环处理完毕以后，进入大循环判断 34 if (i >= 0 && j >= 0){ 35 if (s.charAt(i) != t.charAt(j)){ 36 return false; 37 } 38 }else if (i >= 0 || j >= 0){ 39 // i>=0 且 j >= 0为false的情况 40 // i < 0 且 j >= 0 : 41 // i >= 0 且 j < 0 : 42 //以上两种不满足，其中有一个在还没有遍历完的时候就找到字符，另一个已经遍历完了不符合题意 43 // i < 0 且 j < 0：在0位置找到了#,回退就变成了空字符，符合题意 44 return false; 45 } 46 i--; 47 j--; 48 } 49 return true; 50 } 51 }