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.

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

Constraints

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

Solution

The problem Backspace String Compare can be solved in O(n) time and O(1) space by iterating each string backwards and comparing characters that are not erased.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    bool backspaceCompare(string s, string t)
    {
        for (int i = s.length() - 1, j = t.length() - 1; i >= 0 || j >= 0; i--, j--)
        {
            int backspace;
            for (backspace = 0; i >= 0 && (s[i] == '#' || backspace); i--)
                backspace += s[i] == '#' ? 1 : -1;
            for (backspace = 0; j >= 0 && (t[j] == '#' || backspace); j--)
                backspace += t[j] == '#' ? 1 : -1;

            if (i < 0 || j < 0)
                return i == j;
            if (s[i] != t[j])
                return false;
        }

        return true;
    }
};