LeetCode 844 比較含退格的字符串

力扣 844 比較含退格的字符串 | LeetCode 844 Backspace String Compare | 算盡天下系列第 11 期 | 棧/雙指針

題目描述

給定 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”绝编。

算法與數(shù)據(jù)結構

棧

雙指針

題解

這道題可以用一個棧來模擬退格的操作，遍歷字符串貌踏，遇到新字符就入棧十饥，遇到退格鍵就出棧，最后比較兩個棧內(nèi)的元素是否相等哩俭，非常簡單绷跑。

但是如果要求只使用 O(1) 的空間呢？這道題的難度一下子就可以上升好幾個數(shù)量級凡资。

下面分享一種使用雙指針來完成這道題的方法砸捏，只需要使用 O(1) 的輔助空間。

從前往后遍歷字符串的時候隙赁，遇到一個字符垦藏，我們是沒有辦法知道這個字符最終會不會屬于這個字符串，因為我們沒有辦法知道后面會有多少個退格伞访，但是從后往前遍歷字符串的時候掂骏，我們有辦法知道一個字符是不是屬于這個字符串。

那么厚掷，我們可以從后往前遍歷字符串弟灼，記 i 和 j 分別表示當前兩個字符串的比較位置益涧，初始均為 strlen() - 1辜王。

若當前位置的字符不相等（S[i] != T[j]），則直接 return false 而無需繼續(xù)往前比較于样，若當前位置的字符相等抡爹，那么繼續(xù)往前比較掩驱。

現(xiàn)在還需要處理一個退格的問題。

若遇到 S[i] == '#'，那么就要數(shù)一數(shù)有多少個退格鍵欧穴，每遇到一個退格鍵民逼，skipS++，表示接下來要跳過多少個字符涮帘。那么拼苍，當 skipS > 0 時，我們依舊需要持續(xù)地令 i--; skipS--;调缨，不斷的跳過那些被刪除了的字符映屋。

需要注意的有兩點：一，在這個過程中同蜻，S[i] 依舊有可能等于 '#'，此時我們非但不應該進行 skipS--早处，反而應該進行 skipS++湾蔓。二，在退格操作完成后砌梆，緊接著的那個字符也有可能是 '#'默责，因此退格操作應持續(xù)進行到 S[i] != '#' 為止。

對于 T 也是一樣的咸包。

只要 i 和 j 中有任何一個還大于 0桃序，就應該持續(xù)該過程，直到兩者都小于 0烂瘫，此時輸出 true媒熊。

由于字符串長度可能不等，退格鍵的按下次數(shù)可能會超過已經(jīng)輸入的字符數(shù)坟比，例如 a###########b芦鳍，所以應該時刻注意上面所有的條件判斷中要加上 i >= 0 和 j >= 0 的判斷。

這樣葛账，在上面過程中的任何一處出現(xiàn) (i >= 0 && j < 0) 或者 (i < 0 && j >= 0) 都將是不合法的柠衅。

完整代碼

bool backspaceCompare(char * S, char * T){
    int i = strlen(S) - 1;
    int j = strlen(T) - 1;
    int skipS = 0;
    int skipT = 0;
    while (i >= 0 || j >= 0) {
        while (i >= 0 && S[i] == '#') {
            while (i >= 0 && S[i] == '#') {
                skipS++;
                i--;
            }
            while (i >= 0 && skipS > 0) {
                if (S[i] == '#') {
                    skipS++;
                } else {
                    skipS--;
                }
                i--;
            }
        }
        while (j >= 0 && T[j] == '#') {
            while (j >= 0 && T[j] == '#') {
                skipT++;
                j--;
            }
            while (j >= 0 && skipT > 0) {
                if (T[j] == '#') {
                    skipT++;
                } else {
                    skipT--;
                }
                j--;
            }
        }
        if (i >=0 && j >= 0) {
            if (S[i] != T[j]) {
                return false;
            } else {
                i--;
                j--;
            }
        } else {
            return i < 0 && j < 0;
        }
    }
    return true;
}

官方的題解會更簡潔一些：

class Solution {
    public boolean 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 there may be chars in build(S) or build (T)
            while (i >= 0) { // Find position of next possible char in build(S)
                if (S.charAt(i) == '#') {skipS++; i--;}
                else if (skipS > 0) {skipS--; i--;}
                else break;
            }
            while (j >= 0) { // Find position of next possible char in build(T)
                if (T.charAt(j) == '#') {skipT++; j--;}
                else if (skipT > 0) {skipT--; j--;}
                else break;
            }
            // If two actual characters are different
            if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j))
                return false;
            // If expecting to compare char vs nothing
            if ((i >= 0) != (j >= 0))
                return false;
            i--; j--;
        }
        return true;
    }
}

更多文章，請關注凝神長老和他的朋友們（https://www.jxtxzzw.com）