参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

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都有相应的接口，最后比较的时候，只要比较两个字符串就可以了，比比较栈里的元素方便一些。

代码如下：

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，可以把这块公共逻辑抽离出来，代码精简如下：

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。

代码如下：

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

双指针：

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

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); //截取有效字符串
    }
}

从后往前双指针：

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

双指针

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

双指针

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

双指针法：

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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0844.比较含退格的字符串.md

0844.比较含退格的字符串.md

844.比较含退格的字符串

思路

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

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

其他语言版本

Java

python

Go

JavaScript

TypeScript

Files

0844.比较含退格的字符串.md

Latest commit

History

0844.比较含退格的字符串.md

File metadata and controls

844.比较含退格的字符串

思路

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

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

其他语言版本

Java

python

Go

JavaScript

TypeScript