30-Day LeetCoding Challenge Day 9: Backspace String Compare

Backspace String Compare的input是兩個含”#”關鍵字的字串，我們必須要從頭開始讀這兩個字串，但每當讀到”#”關鍵字時，就要「倒退一格」。當兩個字串依此讀到底時，問是否呈現一樣的結果。

初見此題，第一眼感覺就是：「不難，順著規則走一遍，再比較結果應該就可以。」

於是得解如下：

public class Solution {
    // Two pointers, stack
    public boolean backspaceCompare(String S, String T) {

        return trace(S).equals(trace(T));
    }

    private String trace(String s) {

        Deque<Character> stack = new ArrayDeque<>();
        int length = s.length();

        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);

            if (c == '#') {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.push(c);
            }
        }

        return String.valueOf(stack);

    }
}

這個Solution用了O(n)的時間與O(n)的空間。題目最後有問我們是否能找出空間為O(1)的解，不過，懶了，就這樣吧！

Happy Coding！