🔙 比较含退格的字符串

📝 题目描述

​ 给定s和t两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，则返回true。字符串中的#为退格字符，它的作用是删除前面第一个字符。需要注意的是，如果对空文本输入退格字符#，文本则继续为空。

🚀 示例

🖊️ 题解

栈

​ 根据题意，退格符'#'能够删除其前一个字符。因此，该题可以采用「栈」这一数据结构来解决，具体步骤如下。

1. 分别遍历s和t这两个字符串，并转换成栈。在每一轮遍历中，如果当前字符c不为'#'符号，则将其压入栈中，否则弹出栈顶字符。需要注意的是，在弹出栈顶字符时存在边界问题，即栈为空，此时应不作任何处理。

2. 比较这两个栈所表示的字符串是否相同。

​ ⭐️在步骤②中，可先判断两个栈的大小是否相同，若不相同，则提前返回fasle。

public class Solution {

    public boolean backspaceCompare(String s, String t) {
        Deque<Character> sStack = buildStack(s);
        Deque<Character> tStack = buildStack(t);
        if (sStack.size() != tStack.size()) {
            return false;
        }
        int size = sStack.size();
        for (int i = 0; i < size; i++) {
            if (!sStack.pop().equals(tStack.pop())) {
                return false;
            }
        }
        return true;
    }

    private Deque<Character> buildStack(String str) {
        Deque<Character> stack = new ArrayDeque<>(str.length());
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c != '#') {
                stack.push(c);
                continue;
            }
            if (!stack.isEmpty()) {
                stack.pop();
            }
        }
        return stack;
    }
}

双指针

​ 根据题意，由于退格符'#'只会消除前面的一个字符，对后面的字符没有任何影响，因此该题可以采用双指针并从后往前比较两个字符串的方式来解决，具体步骤如下。

1. 初始化i和j两个指针，分别指向字符串s和字符串t的最后一个字符。

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++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            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;
    }

💭 复杂度分析

​ 基于xxxx的解决方案的复杂度分析如下。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(1)$ 。