LeetCode | 844. 比较含退格的字符串

题目描述

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