844. 比较含退格的字符串

题目描述

输入两个字符串 s 和 t。设想把它们分别逐字符敲进一个空白编辑器，其中字符 # 表示按一次退格键，会删掉前面最后一个字符。

文本已经为空时按退格不起作用，文本仍为空。

如果两个字符串敲完后得到的文本相同，返回 true，否则返回 false。

示例 1

输入：s = "ab#c", t = "ad#c"
输出：true

解释：两者最终都是 "ac"。

示例 2

输入：s = "ab##", t = "c#d#"
输出：true

解释：两者的字符都被退格删光，结果都是空串。

示例 3

输入：s = "a#c", t = "b"
输出：false

解释：s 得到 "c"，t 是 "b"。

数据范围

1 <= s.length, t.length <= 200
s 和 t 只含小写字母和字符 #。

进阶：能否做到 O(n) 时间、O(1) 额外空间？

解题思路：栈重建字符串

编辑器的行为就是一个栈：普通字符入栈，# 弹出栈顶（栈空时忽略）。分别把 s 和 t “打”一遍，比较两个栈的内容是否相同。

为什么正确

处理完前 i 个字符后，栈中内容就是编辑器当前显示的文本。

复杂度分析

时间 O(|s| + |t|)；空间 O(|s| + |t|)。进阶可用从后往前的双指针做到 O(1) 空间。

易错点

栈空时遇到 # 要直接忽略，不能弹出。不要用“删掉 # 前一个字符”的字符串替换，连续的 ## 会出错。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def build(x):
            stack = []
            for ch in x:
                if ch != '#':
                    stack.append(ch)
                elif stack:
                    stack.pop()
            return stack
        return build(s) == build(t)

class Solution {
    String build(String x) {
        StringBuilder stack = new StringBuilder();
        for (char ch : x.toCharArray()) {
            if (ch != '#') {
                stack.append(ch);
            } else if (stack.length() > 0) {
                stack.deleteCharAt(stack.length() - 1);
            }
        }
        return stack.toString();
    }

    public boolean backspaceCompare(String s, String t) {
        return build(s).equals(build(t));
    }
}

class Solution {
public:
    string build(const string& x) {
        string stack;
        for (char ch : x) {
            if (ch != '#') {
                stack.push_back(ch);
            } else if (!stack.empty()) {
                stack.pop_back();
            }
        }
        return stack;
    }

    bool backspaceCompare(string s, string t) {
        return build(s) == build(t);
    }
};

func build(x string) string {
	stack := []byte{}
	for i := 0; i < len(x); i++ {
		if x[i] != '#' {
			stack = append(stack, x[i])
		} else if len(stack) > 0 {
			stack = stack[:len(stack)-1]
		}
	}
	return string(stack)
}

func backspaceCompare(s string, t string) bool {
	return build(s) == build(t)
}

var backspaceCompare = function(s, t) {
    const build = x => {
        const stack = [];
        for (const ch of x) {
            if (ch !== '#') {
                stack.push(ch);
            } else if (stack.length) {
                stack.pop();
            }
        }
        return stack.join('');
    };
    return build(s) === build(t);
};

function backspaceCompare(s: string, t: string): boolean {
    const build = (x: string): string => {
        const stack: string[] = [];
        for (const ch of x) {
            if (ch !== '#') {
                stack.push(ch);
            } else if (stack.length) {
                stack.pop();
            }
        }
        return stack.join('');
    };
    return build(s) === build(t);
}

载入编辑器，自己跑一遍 →

其他解法

栈法直接模拟输入过程，最好写；双指针利用“退格只影响前面”从后往前扫，把空间降到 O(1)。

解法 2：从后往前的双指针时间 O(|s| + |t|)，空间 O(1)

退格只影响前面的字符，所以从末尾往前扫。两个指针各自用 skip 记录还要删掉的字符数：遇到 # 就 skip 加 1，遇到普通字符且 skip > 0 就跳过它并把 skip 减 1，直到停在一个真正保留的字符上。比较两个保留字符，不同或一方已经用尽而另一方没有时返回 false，两方同时用尽返回 true。

只用常数额外空间，还能在第一个不同字符处提前结束，正是题目进阶要求的做法。循环里要同时处理跳过、比较和边界，比栈法更容易写错。

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j = len(s) - 1, len(t) - 1
        skip_s = skip_t = 0
        while i >= 0 or j >= 0:
            while i >= 0:
                if s[i] == '#':
                    skip_s += 1
                elif skip_s > 0:
                    skip_s -= 1
                else:
                    break
                i -= 1
            while j >= 0:
                if t[j] == '#':
                    skip_t += 1
                elif skip_t > 0:
                    skip_t -= 1
                else:
                    break
                j -= 1
            if i >= 0 and j >= 0:
                if s[i] != t[j]:
                    return False
            elif i >= 0 or j >= 0:
                return False
            i -= 1
            j -= 1
        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 (i >= 0) {
                if (s.charAt(i) == '#') skipS++;
                else if (skipS > 0) skipS--;
                else break;
                i--;
            }
            while (j >= 0) {
                if (t.charAt(j) == '#') skipT++;
                else if (skipT > 0) skipT--;
                else break;
                j--;
            }
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) return false;
            } else if (i >= 0 || j >= 0) {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
}

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i = s.size() - 1, j = t.size() - 1;
        int skipS = 0, skipT = 0;
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s[i] == '#') skipS++;
                else if (skipS > 0) skipS--;
                else break;
                i--;
            }
            while (j >= 0) {
                if (t[j] == '#') skipT++;
                else if (skipT > 0) skipT--;
                else break;
                j--;
            }
            if (i >= 0 && j >= 0) {
                if (s[i] != t[j]) return false;
            } else if (i >= 0 || j >= 0) {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
};

func backspaceCompare(s string, t string) bool {
	i, j := len(s)-1, len(t)-1
	skipS, skipT := 0, 0
	for i >= 0 || j >= 0 {
		for i >= 0 {
			if s[i] == '#' {
				skipS++
			} else if skipS > 0 {
				skipS--
			} else {
				break
			}
			i--
		}
		for j >= 0 {
			if t[j] == '#' {
				skipT++
			} else if skipT > 0 {
				skipT--
			} else {
				break
			}
			j--
		}
		if i >= 0 && j >= 0 {
			if s[i] != t[j] {
				return false
			}
		} else if i >= 0 || j >= 0 {
			return false
		}
		i--
		j--
	}
	return true
}

var backspaceCompare = function(s, t) {
    let i = s.length - 1, j = t.length - 1;
    let skipS = 0, skipT = 0;
    while (i >= 0 || j >= 0) {
        while (i >= 0) {
            if (s[i] === '#') skipS++;
            else if (skipS > 0) skipS--;
            else break;
            i--;
        }
        while (j >= 0) {
            if (t[j] === '#') skipT++;
            else if (skipT > 0) skipT--;
            else break;
            j--;
        }
        if (i >= 0 && j >= 0) {
            if (s[i] !== t[j]) return false;
        } else if (i >= 0 || j >= 0) {
            return false;
        }
        i--;
        j--;
    }
    return true;
};

function backspaceCompare(s: string, t: string): boolean {
    let i = s.length - 1, j = t.length - 1;
    let skipS = 0, skipT = 0;
    while (i >= 0 || j >= 0) {
        while (i >= 0) {
            if (s[i] === '#') skipS++;
            else if (skipS > 0) skipS--;
            else break;
            i--;
        }
        while (j >= 0) {
            if (t[j] === '#') skipT++;
            else if (skipT > 0) skipT--;
            else break;
            j--;
        }
        if (i >= 0 && j >= 0) {
            if (s[i] !== t[j]) return false;
        } else if (i >= 0 || j >= 0) {
            return false;
        }
        i--;
        j--;
    }
    return true;
}

栈与堆专题的其他题目

查看栈与堆全部题目 →