栈实现退格字符串比较返回错误，排查代码问题原因

让我帮你拆解这段代码的问题，它主要有两个关键bug导致返回结果不符合预期：

1. 用==比较栈的方式完全错了 #

Java里==是用来比较对象的内存地址的，不是比较内容。哪怕两个栈里的元素完全一模一样，它们是两个独立的对象实例，stack1 == stack2也会返回false。你应该用equals()方法，Stack继承自Vector，它的equals()会逐一比对两个栈里的元素是否完全一致。

2. 空栈调用pop()会直接崩溃 #

比如当字符串开头就是#（像示例3里的T="#a#c"），此时栈还是空的，你直接调用stack2.pop()会抛出EmptyStackException，程序直接报错终止，根本走不到比较的步骤。

修复后的完整代码 #

我把重复的字符串处理逻辑抽成了一个方法，同时修复了这两个问题：

class Solution {
    public boolean backspaceCompare(String S, String T) {
        Stack<Character> stack1 = processInputString(S);
        Stack<Character> stack2 = processInputString(T);
        // 用equals比较栈的内容，而不是==比较引用
        return stack1.equals(stack2);
    }
    
    // 抽公共方法，避免重复代码
    private Stack<Character> processInputString(String str) {
        Stack<Character> stack = new Stack<>();
        for (char c : str.toCharArray()) {
            if (c != '#') {
                stack.push(c);
            } else {
                // 只有栈不为空的时候才执行pop操作
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            }
        }
        return stack;
    }
}

修复点说明 #

• 新增processInputString方法，把两个字符串的处理逻辑统一，减少冗余；
• 执行pop()前先判断栈是否为空，避免空栈异常；
• 用stack1.equals(stack2)替代==，正确比较两个栈的元素内容。

额外的优化思路（不用栈，空间复杂度O(1)） #

如果想进一步优化，不需要额外的栈空间，可以从字符串末尾往前遍历，统计需要跳过的字符数，直接比对最终有效的字符：

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) {
            // 找到S中第一个需要保留的字符
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            // 找到T中第一个需要保留的字符
            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;
    }
}

这个方法不需要额外空间，时间复杂度是O(n+m)，效率更高。

内容的提问来源于stack exchange，提问作者Naveen Verma