一、题目描述

题目直接从 LeetCode 上截图过来，题目如下：

这道题目是要进行向前的消除，当满足条件时，除了消除当前的字符，也会消除当前字符之前的字符，此时可以使用栈结构来进行操作。时间复杂度和空间复杂度，都为O(N)。

本题我使用 Java 语言来完成，LeetCode 给出的 Java 定义如下：

class Solution {
    public boolean backspaceCompare(String s, String t) {

    }
}

二、题目分析

题目中给出两个字符串，分别时 S 和 T。字符串中使用 “#” 表示删除键，会删除它前面的字符，比如 S = “a##c” 这个字符串，字符串的结果为 “c”，T = “#a#c”，字符串的结果也为“c”，这样 S 和 T 是相等的。

画图来模拟整个字符串的过程，如下图。

首先，字符串 S 的值为 “ab#c”，我们依次来遍历每个字符。

第一步，当前字符是 a，字符 a 入栈，当前栈中是 a； 第二步，当前字符是 b，字符 b 入栈，当前栈中是 ab； 第三步，当前字符是 #，字符 # 表示删除键，那么就将前一步的字符删除，即将第二步的字符 b 出栈，当前栈中是 a； 最后一步，当前字符是 c，字符 c 入栈，当前栈中是 ac。

这样，字符串 S 的值为 "ac"。

因为，题目要求是比较 S 和 T 是否相等，那么就把 T 也按照此方法进行处理，处理后出栈进行比较即可。

三、代码实现

看一下我写的 Java 代码，代码如下。

class Solution {
    public boolean backspaceCompare(String s, String t) {
        if (s.length() == 0 && t.length() == 0) {
            return true;
        }

        final Stack<String> ss = new Stack();
        final Stack<String> st = new Stack();

        final int slen = s.length();
        final int tlen = t.length();

        final char del = '#';

        for (int i = 0; i < slen; i ++) {
            if (s.charAt(i) == del && ss.empty()) {
                continue;
            }
            if (s.charAt(i) == del) {
                ss.pop();
                continue;
            }
            ss.push(s.substring(i, i + 1));
        }

        for (int i = 0; i < tlen; i ++) {
            if (t.charAt(i) == del && st.empty()) {
                continue;
            }
            if (t.charAt(i) == del) {
                st.pop();
                continue;
            }
            st.push(t.substring(i, i + 1));
        }

        while (!ss.empty() && !st.empty()) {
            if (!ss.peek().equals(st.peek())) {
                return false;
            }
            ss.pop();
            st.pop();
        }

        if (ss.empty() && st.empty()) {
            return true;
        }

        return false;
    }
}

代码中前两个 for 循环用来完成字符串的处理，后面的 while 循环用来完成两个字符串的比较，代码非常的简单。

四、提交结果

在写完 backspaceCompare 方法体后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们继续修改代码。