844.比較含退格的字符串

給定 s 和 t 兩個(gè)字符串，當(dāng)它們分別被輸入到空白的文本編輯器后，如果兩者相等，返回 true 。# 代表退格字符。

注意：如果對(duì)空文本輸入退格字符，文本繼續(xù)為空。

題目鏈接：844. 比較含退格的字符串 - 力扣（LeetCode）

示例 1：

輸入：s = "ab#c", t = "ad#c"
輸出：true
解釋：s 和 t 都會(huì)變成 "ac"。

示例 2：

輸入：s = "ab##", t = "c#d#"
輸出：true
解釋：s 和 t 都會(huì)變成 ""。

示例 3：

輸入：s = "a#c", t = "b"
輸出：false
解釋：s 會(huì)變成 "c"，但 t 仍然是 "b"。

提示：

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小寫字母以及字符 '#'

進(jìn)階：

• 你可以用 O(n) 的時(shí)間復(fù)雜度和 O(1) 的空間復(fù)雜度解決該問題嗎？

思考：

本題涉及到字符串中的退格問題，所以自然而然就可以想到利用棧的思想來進(jìn)行解決。

當(dāng)然，這道題也可以使用雙指針法來進(jìn)行求解，比較巧妙，但相對(duì)的，這種方法就比較難想到。利用雙指針法可以大大降低空間復(fù)雜度。

利用棧：

本題利用棧的思想是十分簡便的，利用棧先進(jìn)后出的特點(diǎn)，很容易就可以做到對(duì)于字符串中元素的退格。

首先利用一個(gè)Put函數(shù)，將字符串中的元素添加到stack棧容器中，在這個(gè)過程中，就可以實(shí)現(xiàn)元素的退格。接著就可以再backspaceCompare函數(shù)中對(duì)每個(gè)棧頂元素進(jìn)行比較，比較完就出棧，判斷兩個(gè)字符串是否相等。

class Solution {
public:
    void Put(string s, stack<char>& S) {
        for (int i = 0; i < s.size(); i++) { //對(duì)字符串中的元素進(jìn)行遍歷
            if (s[i] == '#' && !S.empty()) S.pop(); //如果是#且S不為空，刪除棧頂元素
            else if (s[i] != '#') S.push(s[i]); //如果該字符串元素不為#，入棧
        }
        return;
    }
    bool backspaceCompare(string s, string t) {
        stack<char> S; //存s的棧
        stack<char> T; //存t的棧
        Put(s, S); //讀入字符串s
        Put(t, T); //讀入字符串t
        if (S.size() - T.size()) return false; //如果長度不一樣，那么肯定內(nèi)容不一樣
        while (!S.empty()) { //遍歷
            if (S.top() != T.top()) return false; //判斷棧首元素
            S.pop(), T.pop(); //刪除
        }
        return true;
    }
};

當(dāng)然，我們也可以利用string完成上述操作：

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        return build(S) == build(T);
    }

    string build(string str) {
        string ret;
        for (char ch : str) {
            if (ch != '#') {
                ret.push_back(ch);
            } else if (!ret.empty()) {
                ret.pop_back();
            }
        }
        return ret;
    }
};

雙指針法：

我們可以注意到： # 號(hào)只會(huì)消除左邊的一個(gè)字符，所以對(duì)右邊的字符無影響，所以我們可以選擇從后往前遍歷。

這里設(shè)置的兩個(gè)指針就不屬于前面所提到的快慢指針或是左右指針，而是用兩個(gè)指針分別指向兩個(gè)字符串的末尾字符，從后往前進(jìn)行遍歷。

設(shè)置變量skipS,skipT分別存放兩個(gè)字符串中#的數(shù)量。

在進(jìn)行從后往前遍歷的過程中：(以字符串S為例)

• 遇到字符為#，skipS++
• 當(dāng)前字符不為#，skipS不為0，skipS--
• 當(dāng)前字符不為#，skipS為0，與T中字符比較，此時(shí)退出S的循環(huán)判斷，開始進(jìn)行T的循環(huán)判斷
• 在S和T都結(jié)束一輪循環(huán)判斷后，對(duì)其當(dāng)前指針?biāo)赶虻脑剡M(jìn)行比較。

class Solution {
public:
   //雙指針法
    bool backspaceCompare(string S, string T) {
        int i = S.length() - 1, j = T.length() - 1; //指針指向尾部
        int skipS = 0, skipT = 0; //初始化

        while (i >= 0 || j >= 0) {
            while (i >= 0) { //先對(duì)S進(jìn)行遍歷，直到尋找到第一個(gè)有效元素
                if (S[i] == '#') {
                    skipS++, i--;
                }
                else if (skipS > 0) {
                    skipS--, i--;
                }
                else {
                    break;
                }
            }
            while (j >= 0) { //再對(duì)T進(jìn)行遍歷，直到尋找到第一個(gè)有效元素
                if (T[j] == '#') {
                    skipT++, j--;
                }
                else if (skipT > 0) {
                    skipT--, j--;
                }
                else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) { //對(duì)此時(shí)S和T的元素進(jìn)行比較
                if (S[i] != T[j]) {
                    return false;
                }
            }
            else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--, j--;
        }
        return true;
    }
};

不足之處在于，這種方法的時(shí)間復(fù)雜度是O（n+m)會(huì)比使用棧要慢一點(diǎn)，屬于是用時(shí)間換空間，空間復(fù)雜度為O（1）。

后續(xù)也會(huì)堅(jiān)持更新我的LeetCode刷題筆記，歡迎大家關(guān)注我，一起學(xué)習(xí)。
如果這篇文章對(duì)你有幫助，或者你喜歡這篇題解，可以給我點(diǎn)個(gè)贊哦。
CSDN同步更新，歡迎關(guān)注我的博客：一粒蛋TT的博客_CSDN博客-LeetCode學(xué)習(xí)筆記,HTML+CSS+JS,數(shù)據(jù)結(jié)構(gòu)領(lǐng)域博主

往期回顧：
LeetCode283.移動(dòng)零
LeetCode27.移除元素
LeetCode26.刪除有序數(shù)組中的重復(fù)項(xiàng)