844.比较退格的字符串
给定 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 <= 200s和t只含有小写字母以及字符'#'
进阶：
- 你可以用
O(n)的时间复杂度和O(1)的空间复杂度解决该问题吗？
思路
本文将给出 空间复杂度O(n)的栈模拟方法 以及空间复杂度是O(1)的双指针方法。
普通方法（使用栈的思路）
这道题目一看就是要使用栈的节奏，这种匹配（消除）问题也是栈的擅长所在
那么本题，确实可以使用栈的思路，但是没有必要使用栈，因为最后比较的时候还要比较栈里的元素，有点麻烦。
// 普通方法（使用栈的思路） class Solution { public boolean backspaceCompare(String s, String t) { StringBuilder ssb = new StringBuilder(); // 模拟栈 StringBuilder tsb = new StringBuilder(); // 模拟栈 // 分别处理两个 String for (char c : s.toCharArray()) { if (c != '#') { ssb.append(c); // 模拟入栈 } else if (ssb.length() > 0){ // 栈非空才能弹栈 ssb.deleteCharAt(ssb.length() - 1); // 模拟弹栈 } } for (char c : t.toCharArray()) { if (c != '#') { tsb.append(c); // 模拟入栈 } else if (tsb.length() > 0){ // 栈非空才能弹栈 tsb.deleteCharAt(tsb.length() - 1); // 模拟弹栈 } } return ssb.toString().equals(tsb.toString()); } }
- 时间复杂度:O(n + m)
- 空间复杂度:O(n + m)
优化方法（从后向前双指针）
当然还可以有使用 O(1) 的空间复杂度来解决该问题。
同时从后向前遍历S和T（i初始为S末尾，j初始为T末尾），记录#的数量，模拟消除的操作，如果#用完了，就开始比较S[i]和S[j]。
如果S[i]和S[j]不相同返回false，如果有一个指针（i或者j）先走到的字符串头部位置，也返回false。
代码如下：
class Solution { public boolean backspaceCompare(String s, String t) { char[] chs1 = s.toCharArray(); char[] chs2 = t.toCharArray(); return solve(chs1).equals(solve(chs2)); } private String solve(char[] chs) { /* 双指针模拟退格 */ int len = chs.length; int slow = -1, fast = 0; while (fast < len) { if (chs[fast] != '#') { // 普通字母直接统计 chs[++slow] = chs[fast]; } else { // 遇到#考虑退格(注意slow只统计非#的字符,并不会覆盖掉fast) if (slow >= 0) slow--; } fast++; } // slow位索引就是最后一个字母位置,索引+1就是个数->生成String return new String(chs, 0, slow + 1); } }
- 时间复杂度：O(n + m)
- 空间复杂度：O(1)
