[leetcode #844] Backspace String Compare

Problem

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Constraints:

· 1 <= s.length, t.length <= 200
· s and t only contain lowercase letters and '#' characters.

Follow up: Can you solve it in O(n) time and O(1) space?

Idea

'#'가 backspace라고 가정할 때 주어진 문자열 s와 문자열 t의 최종 형태가 같은지 확인하는 문제다.

각 문자열에 대한 stack을 사용해 '#'가 나오면 stack에 저장되어 있는 문자를 꺼내면 된다. 문자열 탐색이 끝난 뒤 두 stack을 하나씩 pop해서 문자를 비교하고, 최종적으로 두 stack이 비어있으면 최종 형태가 같은 것이다.

Solution

class Solution {
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> stackForS = new Stack<>();
        Stack<Character> stackForT = new Stack<>();

        for (int i=0; i < s.length(); i++) {
            if (s.charAt(i) == '#') {
                if (!stackForS.isEmpty()) {
                    stackForS.pop();
                }
                continue;
            }
            stackForS.push(s.charAt(i));
        }

        for (int i=0; i < t.length(); i++) {
            if (t.charAt(i) == '#') {
                if (!stackForT.isEmpty()) {
                    stackForT.pop();
                }
                continue;
            }
            stackForT.push(t.charAt(i));
        }

        while (!stackForS.isEmpty() && !stackForT.isEmpty()) {
            if (stackForS.pop() != stackForT.pop()) {
                return false;
            }
        }

        return stackForS.isEmpty() && stackForT.isEmpty();
    }
}

Reference

https://leetcode.com/problems/backspace-string-compare/