844. Backspace String Compare

#### QUESTION:

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

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 = “#a#c” Output: true Explanation: Both S and T become “c”. Example 4:

Input: S = “a#c”, T = “b” Output: false Explanation: S becomes “c” while T becomes “b”. Note:

1 <= S.length <= 200 1 <= 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?

#### SOLUTION:

``````class Solution {
public boolean backspaceCompare(String S, String T) {
Queue<Character> q1 = new ArrayDeque<>();
Queue<Character> q2 = new ArrayDeque<>();
for (char c : S.toCharArray()) {
if (c == '#') q1.poll();
else ((ArrayDeque<Character>) q1).push(c);
}
for (char c : T.toCharArray()) {
if (c == '#') q2.poll();
else ((ArrayDeque<Character>) q2).push(c);
}
if (q1.size() == q2.size()) {
for (int i = 0; i < q1.size(); i++) {
if (q1.poll() != q2.poll()) return false;
}
return true;
}
return false;
}
}
``````
>