力扣844(Java)-比较含退格的字符串（简单）

题目：

给定 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 }