Approach: Build with stack

def backspaceCompare(s, t):
    def build(x):
        st = []
        for c in x:
            if c == "#":
                if st: st.pop()
            else: st.append(c)
        return "".join(st)
    return build(s) == build(t)

Complexity: O(n) time, O(n) space.

Full Solution — all languages

class Solution:
    def backspaceCompare(self, s, t):
        def build(x):
            st = []
            for c in x:
                if c == "#":
                    if st: st.pop()
                else:
                    st.append(c)
            return "".join(st)
        return build(s) == build(t)

import java.util.*;
class Solution {
    public boolean backspaceCompare(String s, String t) {
        return build(s).equals(build(t));
    }
    String build(String x) {
        StringBuilder sb = new StringBuilder();
        for (char c : x.toCharArray()) {
            if (c == '#') {
                if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
            } else sb.append(c);
        }
        return sb.toString();
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: bool backspaceCompare(string s, string t) {
        auto build = [](string x) {
            string st;
            for (char c : x) {
                if (c == '#') {
                    if (!st.empty()) st.pop_back();
                } else st.push_back(c);
            }
            return st;
        };
        return build(s) == build(t);
    }
};

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */ var backspaceCompare = function(s, t) {
    const build = (x) => {
        const st = [];
        for (const c of x) {
            if (c === '#') {
                if (st.length) st.pop();
            } else st.push(c);
        }
        return st.join('');
    };
    return build(s) === build(t);
};

Backspace String Compare

Example 1

Example 2

Example 3

Constraints