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