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.

&nbsp;
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".


&nbsp;
Constraints:


	1 &lt;= s.length, t.length &lt;= 200
	s and t only contain lowercase letters and '#' characters.


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

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def backwardResult(string):
            debt = 0
            
            for c in reversed(string):
                if c == '#':
                    debt += 1
                
                elif debt > 0:
                    debt -= 1
                
                else:
                    yield c
        
        return all(a == b for (a, b) in zip_longest(backwardResult(s), backwardResult(t)))
class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        while(i >= 0 || j >= 0) {
            i = getCurPos(i, s);
            j = getCurPos(j, t);
            if (i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)) return false;
            if ((i >= 0) != (j >= 0)) return false;
            i--;
            j--;
        }
        return true;
    }
    private int getCurPos(int i, String s) {
        int dels = 0;
        while( i >= 0) {
            if (s.charAt(i) == '#') {
                dels++;
                i--;
            } else if (dels > 0) {
                dels--;
                i--;
            } else break;
        }
        return i;
    }
}
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stack<int> st1;
        stack<int> st2;
        int len = s.length();
        int len2 = t.length();

        for(int i=0; i<len; i++){
            if(s[i] != '#'){
                st1.push(s[i]);
            }
            else{
                if(!st1.empty()){
                    st1.pop();
                }
            }
        }
        for(int i=0; i<len2; i++){
            if(t[i] != '#'){
                st2.push(t[i]);
            }
            else{
                if(!st2.empty()){
                    st2.pop();
                }
            }
        }

        while(!st1.empty() && !st2.empty()){
            if(st1.top() != st2.top()){
                return false;
            }
            st1.pop();
            st2.pop();
        }
        if(st1.empty() && st2.empty()){
            return true;
        }
        return false;
    }
};
var backspaceCompare = function(s, t) {
    let stack1 = [];
    let stack2 = [];
    
    for(let i=0; i<s.length; i++) {
        if(s[i] == '#') {
            if(stack1.length != 0) {
                stack1.pop();
            }
        } else {
            stack1.push(s[i]);
        }
    }
    
    for(let j=0; j<t.length; j++) {
        if(t[j] == '#') {
            if(stack2.length != 0) {
                stack2.pop();
            }
        } else {
            stack2.push(t[j]);
        }
    }
    return stack1.join('') === stack2.join('');
};
Backspace String Compare