题目

• 概述：给定两个含退格的字符串，比较这两个字符串的有效部分是否相等

退格表示自己本身和靠近它左侧的第一个字符（如果有的话）是无效字符

• 输入：

1. 字符串S，范围[1, 200]
2. 字符串T，范围[1, 200]

S和T只含有小写字符和退格字符'#'

• 输出：两个字符串的有效部分是否相等

• 出处：https://leetcode-cn.com/problems/backspace-string-compare/

思路

• 由于题目中包含退格这一关键字，可以考虑用栈来做

• 对于将要入栈的字符串S中的字符c，如果c为'#'，则弹出栈顶元素（如果栈不为空的话），否则将c入栈，对字符串T做相同处理

• 依次弹出两个栈中的元素，若所有元素都相等，则两个字符串相等，反之则不相等

代码

class Solution {
    public boolean backspaceCompare(String S, String T) {
        LinkedList<Character> sStack = new LinkedList<>();
        LinkedList<Character> tStack = new LinkedList<>();
        for (char c : S.toCharArray()) {
            if (c == '#') {
                if (!sStack.isEmpty()) {
                    sStack.pop();
                }
            } else {
                sStack.push(c);
            }
        }
        for (char c : T.toCharArray()) {
            if (c == '#') {
                if (!tStack.isEmpty()) {
                    tStack.pop();
                }
            } else {
                tStack.push(c);
            }
        }
        
        while (!sStack.isEmpty() && !tStack.isEmpty()) {
            if (sStack.pop() != tStack.pop()) {
                return false;
            }
        }
        return sStack.isEmpty() && tStack.isEmpty();
    }
}