844. Backspace String Compare

Problem statement

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?

Solution: Build and clean the string using the stack's behaviors

Code

#include <iostream>
#include <vector>
using namespace std;
string cleanString(string &s) {
    vector<char> v;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] != '#') {
            v.push_back(s[i]);
        } else {
            if (!v.empty()) {
                v.pop_back();
            }
        }
    }
    return string(v.begin(), v.end());
}
bool backspaceCompare(string s, string t) {
    return cleanString(s) == cleanString(t);
}
int main() {
    cout << backspaceCompare("ab#c", "ad#c") << endl;
    cout << backspaceCompare("ab##", "c#d#") << endl;
    cout << backspaceCompare("a#c", "b") << endl;
}

Output:
1
1
0

Complexity

• Runtime: O(n), where n = max(s.length, t.length).

• Extra space: O(n).

Implementation notes

Why vector instead of stack?

You can use the methods push and pop of the data structure stack to build and clean the strings.

But vector also has such methods: push_back and pop_back.

On the other hand, using vector it is easier to construct a string by constructor than using stack after cleaning.

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

Yes, you can.

The simplest way is just to perform the erasure directly on strings s and t. But the run time complexity of string::erase is not constant.

References

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

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.