比较含退格的数据算法字符串

力扣题目链接：https://leetcode-cn.com/problems/backspace-string-compare

给定 S 和 T 两个字符串，当它们分别被输入到空白的结构较含文本编辑器后，判断二者是退格否相等，并返回结果。符串# 代表退格字符。数据算法

注意：如果对空文本输入退格字符，结构较含文本继续为空。退格

示例 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 = "#a#c" 输出：true 解释：S 和 T 都会变成 “c”。

示例 4：

输入：S = "a#c",退格 T = "b" 输出：false 解释：S 会变成 “c”，但 T 仍然是符串 “b”。

思路

本文将给出 空间复杂度的数据算法栈模拟方法 以及空间复杂度是的双指针方法。

普通方法(使用栈的结构较含思路)

这道题目一看就是要使用栈的节奏，这种匹配(消除)问题也是退格栈的擅长所在，跟着一起刷题的同学应该知道，在栈与队列：匹配问题都是栈的强项，我就已经提过了一次使用栈来做类似的事情了。服务器托管

那么本题，确实可以使用栈的思路，但是没有必要使用栈，因为最后比较的时候还要比较栈里的元素，有点麻烦。

这里直接使用字符串string，来作为栈，末尾添加和弹出，string都有相应的接口，最后比较的时候，只要比较两个字符串就可以了，比比较栈里的元素方便一些。

代码如下：

class Solution {  public:     bool backspaceCompare(string S, string T) {          string s; // 当栈来用         string t; // 当栈来用         for (int i = 0; i < S.size(); i++) {              if (S[i] != #) s += S[i];             else if (!s.empty()) {                  s.pop_back();         }         for (int i = 0; i < T.size(); i++) {              if (T[i] != #) t += T[i];             else if (!t.empty()) {                  t.pop_back();             }         }         if (s == t) return true; // 直接比较两个字符串是否相等，比用栈来比较方便多了         return false;     } }; 

时间复杂度:，n为S的长度，m为T的长度 ，也可以理解是的时间复杂度

空间复杂度:当然以上代码，大家可以发现有重复的逻辑处理S，处理T，可以把这块公共逻辑抽离出来，云服务器代码精简如下：

class Solution {  private: string getString(const string& S) {      string s;     for (int i = 0; i < S.size(); i++) {          if (S[i] != #) s += S[i];         else if (!s.empty()) {              s.pop_back();         }     }     return s; } public:     bool backspaceCompare(string S, string T) {          return getString(S) == getString(T);     } }; 

性能依然是：

时间复杂度： 空间复杂度：

优化方法(从后向前双指针)

当然还可以有使用 的空间复杂度来解决该问题。

同时从后向前遍历S和T(i初始为S末尾，j初始为T末尾)，记录#的数量，模拟消除的操作，如果#用完了，就开始比较S[i]和S[j]。

动画如下：

如果S[i]和S[j]不相同返回false，如果有一个指针(i或者j)先走到的字符串头部位置，也返回false。

代码如下：

class Solution {  public:     bool backspaceCompare(string S, string T) {          int sSkipNum = 0; // 记录S的#数量         int tSkipNum = 0; // 记录T的#数量         int i = S.size() - 1;         int j = T.size() - 1;         while (1) {              while (i >= 0) {  // 从后向前，消除S的#                 if (S[i] == #) sSkipNum++;                 else {                      if (sSkipNum > 0) sSkipNum--;                     else break;                 }                 i--;             }             while (j >= 0) {  // 从后向前，消除T的#                 if (T[j] == #) tSkipNum++;                 else {                      if (tSkipNum > 0) tSkipNum--;                     else break;                 }                 j--;             }             // 后半部分#消除完了，接下来比较S[i] != T[j]             if (i < 0 || j < 0) break; // S 或者T 遍历到头了             if (S[i] != T[j]) return false;             i--;j--;         }         // 说明S和T同时遍历完毕         if (i == -1 && j == -1) return true;         return false;     } };  时间复杂度： 空间复杂度：

其他语言版本

Java：

// 普通方法（使用栈的思路） 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());     } } 

python

class Solution:     def get_string(self, s: str) -> str :         bz = []         for i in range(len(s)) :             c = s[i]             if c != # :                 bz.append(c) # 模拟入栈             elif len(bz) > 0: # 栈非空才能弹栈                 bz.pop() # 模拟弹栈         return str(bz)     def backspaceCompare(self, s: str, t: str) -> bool:         return self.get_string(s) == self.get_string(t)         pass 

Go

func getString(s string) string {   bz := []rune{ }  for _, c := range s {    if c != # {     bz = append(bz, c); // 模拟入栈   } else if len(bz) > 0 {  // 栈非空才能弹栈    bz = bz[:len(bz)-1] // 模拟弹栈   }  }  return string(bz) } func backspaceCompare(s string, t string) bool {   return getString(s) == getString(t) } 

 JavaScript

// 双栈 var backspaceCompare = function(s, t) {  const arrS = [], arrT = []; // 数组作为栈使用 for(let char of s){  char === # ? arrS.pop() : arrS.push(char); } for(let char of t){  char === # ? arrT.pop() : arrT.push(char); } return arrS.join() === arrT.join(); // 比较两个字符串是否相等 }; //双栈精简 var backspaceCompare = function(s, t) {  const getString = s => {  let arrS = []; for(let char of s){  char === # ? arrS.pop() : arrS.push(char); } return arrS.join(); } return getString(s) === getString(t); }; //双指针 var backspaceCompare = function(s, t) {  let sSkipNum = 0; // 记录s的#数量 let tSkipNum = 0; // 记录t的#数量 let i = s.length - 1, j = t.length - 1; while(true) {  while(i >= 0){  // 从后向前，消除s的# if(s[i] === #) sSkipNum++; else {  if (sSkipNum > 0) sSkipNum--; else break; } i--; } while (j >= 0) {  // 从后向前，消除t的# if (t[j] === #) tSkipNum++; else {  if (tSkipNum > 0) tSkipNum--; else break; } j--; } // 后半部分#消除完了，接下来比较s[i] != t[j] if (i < 0 || j < 0) break; // s 或者t 遍历到头了 if (s[i] !== t[j]) return false; i--;j--; } // 说明s和t同时遍历完毕 if (i == -1 && j == -1) return true; return false; };