[[441739]]

比較含退格的字符串

力扣題目鏈接：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; 
 
};