#   # 844. Backspace String Compare

## Using std::vector as a std::stack

### 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

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