### 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”**.*