844.比较含退格的字符串

力扣题目链接

给定 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”。

思路

本文将给出空间复杂度O(n)的栈模拟方法以及空间复杂度是O(1)的双指针方法。

普通方法（使用栈的思路）

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

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

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

代码如下：

C++
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;
    }
};

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

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

C++
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);
    }
};

性能依然是：

时间复杂度：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。

代码如下：

C++
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;
    }
};

时间复杂度：O(n + m)
空间复杂度：O(1)

其他语言版本

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());
    }
}

双指针：

Java
class Solution {
public static boolean backspaceCompare(String s, String t) {
        char[] sarray = s.toCharArray();
        char[] tarray = t.toCharArray();
        return generate(sarray).equals(generate(tarray));
    }
    public static String generate(char[] a){
        int slow = -1;
        int fast = 0;
        if(a.length == 1){
            return new String(a);
        } else{
            for(fast = 0; fast < a.length; fast++){
                if(a[fast] != '#')
                    a[++slow] = a[fast];
                else{
                    if(slow >= 0)
                        slow--;
                }
            }
            return new String(a,0,slow + 1);
        }
    }
}

Java
class Solution {
    public static boolean backspaceCompare(String s, String t) {
        return getStr(s).equals(getStr(t));
    }

    public static String getStr(String s) { //使用快慢双指针去除字符串中的#
        int slowIndex;
        int fastIndex = 0;
        StringBuilder builder = new StringBuilder(s); //StringBuilder用于修改字符串
        for(slowIndex = 0; fastIndex < s.length(); fastIndex++) {
            if(builder.charAt(fastIndex) != '#') {
                builder.setCharAt(slowIndex++,builder.charAt(fastIndex));
            } else {
                if(slowIndex > 0) {
                    slowIndex--;
                }
            }
        }
        return builder.toString().substring(0,slowIndex); //截取有效字符串
    }
}

从后往前双指针：

Java
class Solution {
    public static boolean backspaceCompare(String s, String t) {
        int sSkipNum = 0; //记录s的#的个数
        int tSkipNum = 0; //记录t的#的个数
        int sIndex = s.length() - 1;
        int tIndex = t.length() - 1;
        while(true) {
            while(sIndex >= 0) { //每次记录连续的#并跳过被删除的字符
                if(s.charAt(sIndex) == '#') {
                    sSkipNum++;
                } else {
                    if(sSkipNum > 0) {
                        sSkipNum--;
                    } else {
                        break;
                    }
                }
                sIndex--;
            }
            while(tIndex >= 0) { //每次记录连续的#并跳过被删除的字符
                if(t.charAt(tIndex) == '#') {
                    tSkipNum++;
                } else {
                    if(tSkipNum > 0) {
                        tSkipNum--;
                    } else {
                        break;
                    }
                }
                tIndex--;
            }
            if(sIndex < 0 || tIndex < 0) { //s 或者 t遍历完了
                break;
            }
            if(s.charAt(sIndex) != t.charAt(tIndex)) { //当前下标的字符不相等
                return false;
            }
            sIndex--;
            tIndex--;
        }
        if(sIndex == -1 && tIndex == -1) { //同时遍历完 则相等
            return true;
        }
        return false;
    }
}

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

双指针

Python
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        s_index, t_index = len(s) - 1, len(t) - 1
        s_backspace, t_backspace = 0, 0 # 记录s,t的#数量
        while s_index >= 0 or t_index >= 0: # 使用or，以防长度不一致
            while s_index >= 0: # 从后向前，消除s的#
                if s[s_index] == '#':
                    s_index -= 1
                    s_backspace += 1
                else:
                    if s_backspace > 0:
                        s_index -= 1
                        s_backspace -= 1
                    else:
                        break
            while t_index >= 0: # 从后向前，消除t的#
                if t[t_index] == '#':
                    t_index -= 1
                    t_backspace += 1
                else:
                    if t_backspace > 0:
                        t_index -= 1
                        t_backspace -= 1
                    else:
                        break
            if s_index >= 0 and t_index >= 0: # 后半部分#消除完了，接下来比较当前位的值
                if s[s_index] != t[t_index]:
                    return False
            elif s_index >= 0 or t_index >= 0: # 一个字符串找到了待比较的字符，另一个没有，返回False
                return False
            s_index -= 1
            t_index -= 1
        return True

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)
}

双指针

Go
func backspaceCompare(s string, t string) bool {
    s_index, t_index := len(s) - 1, len(t) - 1
    s_backspace, t_backspace := 0, 0 // 记录s,t的#数量
    for s_index >= 0 || t_index >= 0 { // 使用or，以防长度不一致
        for s_index >= 0 { // 从后向前，消除s的#
            if s[s_index] == '#' {
                s_index--
                s_backspace++
            } else {
                if s_backspace > 0 {
                    s_index--
                    s_backspace--
                } else {
                    break
                }
            }
        }
        for t_index >= 0 { // 从后向前，消除t的#
            if t[t_index] == '#' {
                t_index--
                t_backspace++
            } else {
                if t_backspace > 0 {
                    t_index--
                    t_backspace--
                } else {
                    break
                }
            }
        }
        if s_index >= 0 && t_index >= 0 { // 后半部分#消除完了，接下来比较当前位的值
            if s[s_index] != t[t_index] {
                return false
            }
        } else if s_index >= 0 || t_index >= 0 { // 一个字符串找到了待比较的字符，另一个没有，返回false
            return false
        }
        s_index--
        t_index--
    }
    return true
}

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;
};

双栈法：

TypeScript
function backspaceCompare(s: string, t: string): boolean {
    const stack1: string[] = [],
        stack2: string[] = [];
    for (let c of s) {
        if (c === '#') {
            stack1.pop();
        } else {
            stack1.push(c);
        }
    }
    for (let c of t) {
        if (c === '#') {
            stack2.pop();
        } else {
            stack2.push(c);
        }
    }
    if (stack1.length !== stack2.length) return false;
    for (let i = 0, length = stack1.length; i < length; i++) {
        if (stack1[i] !== stack2[i]) return false;
    }
    return true;
};

双指针法：

TypeScript
function backspaceCompare(s: string, t: string): boolean {
    let sIndex: number = s.length - 1,
        tIndex: number = t.length - 1;
    while (true) {
        sIndex = getIndexAfterDel(s, sIndex);
        tIndex = getIndexAfterDel(t, tIndex);
        if (sIndex < 0 || tIndex < 0) break;
        if (s[sIndex] !== t[tIndex]) return false;
        sIndex--;
        tIndex--;
    }
    return sIndex === -1 && tIndex === -1;
};
function getIndexAfterDel(s: string, startIndex: number): number {
    let backspaceNum: number = 0;
    while (startIndex >= 0) {
        // 不可消除
        if (s[startIndex] !== '#' && backspaceNum === 0) break;
        // 可消除
        if (s[startIndex] === '#') {
            backspaceNum++;
        } else {
            backspaceNum--;
        }
        startIndex--;
    }
    return startIndex;
}

双指针

Rust
impl Solution {
    pub fn backspace_compare(s: String, t: String) -> bool {
        let (s, t) = (
            s.chars().collect::<Vec<char>>(),
            t.chars().collect::<Vec<char>>(),
        );
        Self::get_string(s) == Self::get_string(t)
    }

    pub fn get_string(mut chars: Vec<char>) -> Vec<char> {
        let mut slow = 0;
        for i in 0..chars.len() {
            if chars[i] == '#' {
                slow = (slow as u32).saturating_sub(1) as usize;
            } else {
                chars[slow] = chars[i];
                slow += 1;
            }
        }
        chars.truncate(slow);
        chars
    }
}

双栈法

Rust
impl Solution {
    pub fn backspace_compare(s: String, t: String) -> bool {
        Self::get_string(s) == Self::get_string(t)
    }

    pub fn get_string(string: String) -> String {
        let mut s = String::new();
        for c in string.chars() {
            if c != '#' {
                s.push(c);
            } else if !s.is_empty() {
                s.pop();
            }
        }
        s
    }
}

思路​

普通方法（使用栈的思路）​

优化方法（从后向前双指针）​

其他语言版本​

思路

普通方法（使用栈的思路）

优化方法（从后向前双指针）

其他语言版本